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 )=1
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
10
10^1
10^2
10^3
10^4
10^5
10^6
10^7
10^8
10^9
10^10
pi(x)
4
25
168
1086
9592
78498
664,579
5,761,455
50847534
455052512
x/log(x)
4.3
21.7
144.9
1086
8686
72464
621118
5434780
48309180
434294482
pi(x)/(x logx)
0.93
1.15
1.16
1.11
1.10
1.08
1.07
1.06
1.05
1.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)1
Current best factorising algorithms are the
Number Field Seive (NFS) being the fastest known
factorising algorithm for larger than 100 digits.
Quadratic seive(QS),the fastest known factorising
algorithm
for factorising numbers less than 110 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 10^n & 10^(n+1) 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.1minutes
to generate a 1024 bit (128 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 )=1
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
10
10^1
10^2
10^3
10^4
10^5
10^6
10^7
10^8
10^9
10^10
pi(x)
4
25
168
1086
9592
78498
664,579
5,761,455
50847534
455052512
x/log(x)
4.3
21.7
144.9
1086
8686
72464
621118
5434780
48309180
434294482
pi(x)/(x logx)
0.93
1.15
1.16
1.11
1.10
1.08
1.07
1.06
1.05
1.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)1
Current best factorising algorithms are the
Number Field Seive (NFS) being the fastest known
factorising algorithm for larger than 100 digits.
Quadratic seive(QS),the fastest known factorising
algorithm
for factorising numbers less than 110 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 10^n & 10^(n+1) 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.1minutes
to generate a 1024 bit (128 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.