DATA
03-28-2002, 09:40 AM
hi,
The security of the RSA lies in the difficulty of
factorising into large primes.
Here are a few observations
Theorom:There are infinitely many primes.
Consider a function pi(x) which counts the number of
primes
less than or equal to x. i.e pi(x)<=x
Thus pi(x)=number of primes satisfying 2<=p<=x
Prime number theorom.
Lim [x->infinity] ( ( pi(x)logx ) /x )=*
Log x being the naturally logarithm of x.
Here is a statical table relating them.
Let ^ denote exponent
One would need to reconstruct the table below
x
*0
*0^*
*0^2
*0^*
*0^4
*0^5
*0^6
*0^7
*0^8
*0^*
*0^*0
pi(x)
4
25
*68
*086
*5*2
784*8
664,57*
5,76*,455
508475*4
4550525*2
x/log(x)
4.*
2*.7
*44.*
*086
8686
72464
62***8
54*4780
48*0**80
4*42*4482
pi(x)/(x logx)
0.**
*.*5
*.*6
*.**
*.*0
*.08
*.07
*.06
*.05
*.048
One would need to put this table like
x pi(x) x/log x pi(x)/(x/logx)
and their corresponding values vertically.
Doesn't see to be my lucky day :)
By examining the statistics above,though there are no
end prime numbers they become more widely distributed
as we go down the statical table.
From the prime number theorom ,it is clear that for
very large values of x, ( pi(x)logx )/x ->(tends to)*
Current best factorising algorithms are the
Number Field Seive (NFS) being the fastest known
factorising algorithm for larger than *00 digits.
Quadratic seive(QS),the fastest known factorising
algorithm
for factorising numbers less than **0 digits.The
fastest variant of the
QS being the double large prime variation of the
multiple polynomial Quadratic seive.
The most trivial method ofcourse is to test every
prime number less than or
equal to the square root of the candidate.
As computers become faster and factorising algorithms
get
better,the need for generating bigger prime numbers
arise.
the probability of finding prime numbers
between *0^n & *0^(n+*) greatly diminishes for large
values of n.
Would it be then,with time worth using the
RSA,finding very large primes ,then their product,
both of the operations which are presently very slow.
What would be hence the scenario of the future when
it would need to find even larger primes & their
products?
On a SPARC 2,it takes an average of 5.*minutes
to generate a *024 bit (*28 byte ) prime.As far as I
know they used the Rabin-Miller method to generate
the prime number.
The question is RSA woRth all this much.Wouldn't
the time come when prime numbers so large need
to be generated,whose speed of operation will be
drastically reduced and become infesible to generate
session keys for real time applications?
Regards Data.
The security of the RSA lies in the difficulty of
factorising into large primes.
Here are a few observations
Theorom:There are infinitely many primes.
Consider a function pi(x) which counts the number of
primes
less than or equal to x. i.e pi(x)<=x
Thus pi(x)=number of primes satisfying 2<=p<=x
Prime number theorom.
Lim [x->infinity] ( ( pi(x)logx ) /x )=*
Log x being the naturally logarithm of x.
Here is a statical table relating them.
Let ^ denote exponent
One would need to reconstruct the table below
x
*0
*0^*
*0^2
*0^*
*0^4
*0^5
*0^6
*0^7
*0^8
*0^*
*0^*0
pi(x)
4
25
*68
*086
*5*2
784*8
664,57*
5,76*,455
508475*4
4550525*2
x/log(x)
4.*
2*.7
*44.*
*086
8686
72464
62***8
54*4780
48*0**80
4*42*4482
pi(x)/(x logx)
0.**
*.*5
*.*6
*.**
*.*0
*.08
*.07
*.06
*.05
*.048
One would need to put this table like
x pi(x) x/log x pi(x)/(x/logx)
and their corresponding values vertically.
Doesn't see to be my lucky day :)
By examining the statistics above,though there are no
end prime numbers they become more widely distributed
as we go down the statical table.
From the prime number theorom ,it is clear that for
very large values of x, ( pi(x)logx )/x ->(tends to)*
Current best factorising algorithms are the
Number Field Seive (NFS) being the fastest known
factorising algorithm for larger than *00 digits.
Quadratic seive(QS),the fastest known factorising
algorithm
for factorising numbers less than **0 digits.The
fastest variant of the
QS being the double large prime variation of the
multiple polynomial Quadratic seive.
The most trivial method ofcourse is to test every
prime number less than or
equal to the square root of the candidate.
As computers become faster and factorising algorithms
get
better,the need for generating bigger prime numbers
arise.
the probability of finding prime numbers
between *0^n & *0^(n+*) greatly diminishes for large
values of n.
Would it be then,with time worth using the
RSA,finding very large primes ,then their product,
both of the operations which are presently very slow.
What would be hence the scenario of the future when
it would need to find even larger primes & their
products?
On a SPARC 2,it takes an average of 5.*minutes
to generate a *024 bit (*28 byte ) prime.As far as I
know they used the Rabin-Miller method to generate
the prime number.
The question is RSA woRth all this much.Wouldn't
the time come when prime numbers so large need
to be generated,whose speed of operation will be
drastically reduced and become infesible to generate
session keys for real time applications?
Regards Data.