Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let’s have $N_1=p^a$ where $p$ a prime number and $a$ a natural number. If we want to find all numbers from $1-N_1$ which are not divisible by $p$ we have to subtract all multiples of $p$ from $N_1$. The multiples are $1p,2p,...p^{a-1}p$. From this we conclude that the numbers not divisible by $p$ are $p^a-p^{a-1}$ or $N_1-N_1/p$. Let’s have the product of two primes $p^a q^b=N_2$ where $b$ a natural number. Now we have to find which numbers from $1-N_2$ are not divisible by $p,q$. In order to do so we have to subtract from $N_2$ the multiples $N_2/p$ and $N_2/q$. Now we have $(N_2-N_2/p)-N_2/q$, but some numbers are multiples of $pq$. We can subtract these multiples from $N_2/p$ or $N_2/q$. Let’s subtract them from $N_2/q$, giving $N_2/q-N_2/pq$. The last result has to be subtracted from the first term $(N_2-N_2/p)$. So we have $(N_2-N_2/p)-(N_2/q-N_2/pq)=F(N_2)$. So the number $F(N_2)$ is counting the numbers from $1-N_2$ which are not divisible by $p,q,pq$.

We obtain the second term by applying the ABROZ technique. This works as follows: we multiply the first term by $1/q$ and we obtain$ (N_2-N_2/p) 1/q=(N_2/q-N_2/pq)$. Let’s have $N_3=p^a q^b f^c$ where $ f$ a prime number and $c$ a natural number. We know how to get the first two terms and now have to obtain the third term which contains the multiples of $f$.

We again apply the technique, multiplying the two terms by $1/f$. So we have $(N_3-N_3/p)-(N_3/q-N_3/pq) 1/f=N_3/f-N_3/pf-N_3/qf-N_3/pqf$. To find $F(N_3)$ we subtract from the two terms the third term.

So we have: $F(N_3)=(N_3-N_3/p)-(N_3/q-N_3/pq)-(N_3/f-N_3/pf-N_3/qf-N_3/pqf)$.

We can continue this process indefinitely. The last equation can also be written as $F(N_3)=N_3[1-1/p-1/q+1/pq-1/f+1/pf+1/qf-1/pqf]$. The result inside the bracket can be obtained by multiplication of the three primes as follows: $(1-1/p)(1-1/q)(1-1/f)=[1-1/p-1/q+1/pq-1/f+1/pf+1/qf-1/pqf]$.

So we have $F(N_3)=N_3(1-1/p)(1-1/q)(1-1/f)$. We can make keys when$ F(N)/N$ is minimum or maximum.

My first question is: when is it easier to attack RSA, when $F(N)/N$ is minimum or maximum? Secondly, in what other areas of mathematics can we apply the maximum and minimum ratios?

share|improve this question
1  
Formulas for the most vulnerable ratios for RSA private keys have already been found. There are exactly eight formulas for the eight different ranges of ratio that are hazardous to RSA. Great time and effort was placed on discovering these formula. –  user62572 Feb 16 '13 at 18:45
add comment

2 Answers 2

up vote 2 down vote accepted

$F(N)$ doesn't have a maximum (for $N\gt1$), and it doesn't have a minimum. It can be made arbitrarily close to, but not equal to, zero, and it can be made arbitrarily close to, but not equal to, one. As Yuval suggests, RSA implementations are usually taken with $N=pq$ with $p$ and $q$ large primes, and this will lead to $F(N)$ close to one.

share|improve this answer
    
@Gerry.This is the correct answer. –  Vassilis Parassidis Mar 11 '12 at 3:55
add comment

The function $F$ is usually knows as Euler's phi function. The "hard" case for RSA is usually considered to be when $n$ is a product of two primes of roughly equal magnitude. One reason is that many factorization algorithms run in time that depends on the smallest prime factor of $n$.

share|improve this answer
    
@Yuval.Are you suggesting the ratio has to be maximum? –  Vassilis Parassidis Mar 10 '12 at 22:34
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.