For new authors:
free, easy and fast
For registered authors
Technical Report, 2013
10 Pages
For a given integer n, the number of integers that are relatively prime to n is given by the Euler Phi function [1]. A semi-prime is a number which is a product of two different prime numbers. For example, 21 is the product of 3 and 7 where both 3 and 7 are primes and therefore 21 is a semi-prime. The Euler Phi function has applications to factoring and can be applied towards factoring semi-primes. In this article, the importance of the Euler Phi function will be discussed with respect to factoring semi-primes and an approximation for Euler Phi will be given.
Euler Phi and Factoring Semi-primes
The definition of Euler Phi of n where n is a semi-prime is given by the formula :=
illustration not visible in this excerpt
Multiplying the terms, we then have :=
illustration not visible in this excerpt
Solving for pq, we t hen have :=
illustration not visible in this excerpt
Note that pq is n as n is the product of p and q, therefore :=
illustration not visible in this excerpt
Now, letting x = p + q, we can write that n is :=
illustration not visible in this excerpt
Finally, solving for x, gives :=
illustration not visible in this excerpt
Thus, x = p + q is equal to n – φ(n) + 1.
Recall from the Quadratic formula, that if n = pq, we can develop an expression for which the
Quadratic formula will provide a solution. Consider:
illustration not visible in this excerpt
Where n = pq, and the general equation is :=
ax2 +bx + c = 0
Therefore, by substitution into the Quadratic formula [2] :=
illustration not visible in this excerpt
We have the following solution :=
illustration not visible in this excerpt
Since we have a = 1, b = p + q, and c = n = pq. As an example, consider the expression :=
illustration not visible in this excerpt
Using Equation 2 above, we have :=
illustration not visible in this excerpt
Solving in this case yields factors 3 and 7 which indeed are the divisors of n=3*7=21. This implies
that if the number 10 is known, one can factor the semi-prime 21. Notice that 10 is the sum of the prime divisors of 21, or p + q. However, p + q is given by Equation 1 above, thus :=
illustration not visible in this excerpt
And this in turn allows for a factoring algorithm to be developed utilizing n, a given semi-prime, and
the computation of Euler Phi of n. Given Equation 3, the sum of the divisors of n can be computed and
then plugged into Equation 2 to produce the prime factors p and q of n. An example implementation using Pari/GP [4] number system is as follows :=
illustration not visible in this excerpt
Which yields the following results :=
parisize = 4000000, primelimit = 500000
illustration not visible in this excerpt
The computation of Euler Phi is as difficult as factoring a semi-prime. It is desirable to have some way of computing Euler Phi in polynomial time. However, at the time of this writing, no such method exits [1]. Current computations may proceed by factoring and then computing Euler Phi using the factorization. Consider the following number :=
illustration not visible in this excerpt
where p is a prime factor and p * p is the square of that factor. Then, Euler Phi of n is :=
illustration not visible in this excerpt
but p is the square root of n. Thus, we could compute Euler Phi of n in this case as :=
(√n – 1)2 (Equation 4)
As it turns out, Equation 4 can be used as an approximation to Euler Phi for semi-primes, however, the result varies based on how different p and q are from one another. Where there is a small difference,
the approximation yields the right answer or an answer close enough to the right answer to be useful. As the selection of n increases in size, so does the size of p and q, and thus the difference increases between p and q and the approximation fails to yield a good result in cases where n is sufficiently large. Nevertheless, the following C++ code is used to first generate a set of semi-primes, and then compute their Euler Phi values as well as the values of the Approximation.
Abbildung in dieser Leseprobe nicht enthalten
Where bsieve [3] is a number sieve that generates prime numbers up to a maximum amount, and where the two for loops generate all possible combinations of n choose 2 from the set, i.e., all possible pairs. The final for loop outputs the results. In this example, the maximum prime that can be used is a 32bit integer and the two for loops will take O(N2) time to complete. Given MAX_PRIME is set to 10000, there was 755835 unique semi-primes. The largest value semi-prime not counting squares was n= 99400891 with factors p= 9967 q= 9973. The average difference between the real Euler Phi and the approximation for this set of semi-primes was just 1260.2. In fact, graphing this data yields no important visual clues as the data basically prints out to be a straight line representing Euler Phi for this set of semi-primes with some data points varying.
[...]
Bachelor Thesis, 26 Pages
Diploma Thesis, 154 Pages
Seminar Paper, 29 Pages
English Language and Literature Studies - Linguistics
Term Paper (Advanced seminar), 28 Pages
Engineering - Mechanical Engineering
Doctoral Thesis / Dissertation, 152 Pages
Business economics - Business Management, Corporate Governance
Research Paper (undergraduate), 29 Pages
Pre-University Paper, 20 Pages
GRIN Publishing, located in Munich, Germany, has specialized since its foundation in 1998 in the publication of academic ebooks and books. The publishing website GRIN.com offer students, graduates and university professors the ideal platform for the presentation of scientific papers, such as research projects, theses, dissertations, and academic essays to a wide audience.
Free Publication of your term paper, essay, interpretation, bachelor's thesis, master's thesis, dissertation or textbook - upload now!