DH/ElGamal suitable primes
Tom St Denis
primes of the form: p = 2p' + 1, where p' is prime.
These are ideal since they have large sub-groups for virtually all bases
which make sub-group attacks like those on older implementations of DSA
infeasible.
I have primes of varying size from 16-bits [just for fun] upto 1792-bits.
http://tomstdenis.home.dhs.org/primes.txt
Tom
--
.sig powered by Windows.
Incognito Innominatus
> Just a quick tid-bit. I'm running an IDLE level sieve for ideal DH
> primes of the form: p = 2p' + 1, where p' is prime.
>
> These are ideal since they have large sub-groups for virtually all bases
> which make sub-group attacks like those on older implementations of DSA
> infeasible.
Foolish boy,
There are no sub-group attacks on "older implementations of DSA".
DSA does not use strong primes of the type you describe, as that would
remove one of the main advantages of DSA, compact signatures. DSA is
designed to use small subgroups of a size balanced with the size of
the prime. For 512-1024 bit primes, a subgroup of size 160 bits is a
good balance, as both provide about 80 bits of strength. Using a 160
bit subgroup allows the signatures to fit in 40 bytes. If strong primes
like you are creating were used, the signature would be 256 bytes with
a 1024 bit prime.
For new readers of this newsgroup, Tom St Denis is a teenager who knows
much less than he pretends. Yet he is one of the first to respond to
innocent questions. If the question is something he doesn't know the
answer to, he'll just guess and give bad information. If he does know
the answer, he'll refuse to help in a snotty way and demand that the
poor poster figure out the answer himself.
By his conduct here, Tom St Denis has forfeited any respect or
consideration by others to which he might have been entitled.
Tom St Denis
> Tom St Denis writes:
>
>>Just a quick tid-bit. I'm running an IDLE level sieve for ideal DH
>>primes of the form: p = 2p' + 1, where p' is prime.
>>
>>These are ideal since they have large sub-groups for virtually all bases
>>which make sub-group attacks like those on older implementations of DSA
>>infeasible.
>>
>
> Foolish boy,
>
> There are no sub-group attacks on "older implementations of DSA".
Sorry I meant to write "attacks like those on older implementations of DSA".
I'm well aware of how DSA works.
> For new readers of this newsgroup, Tom St Denis is a teenager who knows
> much less than he pretends. Yet he is one of the first to respond to
> innocent questions. If the question is something he doesn't know the
> answer to, he'll just guess and give bad information. If he does know
> the answer, he'll refuse to help in a snotty way and demand that the
> poor poster figure out the answer himself.
>
> By his conduct here, Tom St Denis has forfeited any respect or
> consideration by others to which he might have been entitled.
Yadadada. Join the "We hate Tom" club and get over yourself.
Tom
Tom St Denis
> Incognito Innominatus wrote:
>
>> Tom St Denis writes:
>>
>>> Just a quick tid-bit. I'm running an IDLE level sieve for ideal DH
>>> primes of the form: p = 2p' + 1, where p' is prime.
>>>
>>> These are ideal since they have large sub-groups for virtually all
>>> bases which make sub-group attacks like those on older
>>> implementations of DSA infeasible.
>>>
>>
>> Foolish boy,
>>
>> There are no sub-group attacks on "older implementations of DSA".
>
>
>
> Sorry I meant to write "attacks like those on older implementations of
> DSA".
More specifically.
"Minding your p's and q's", Ross Anderson and Serge Vaudenay.
Where they show off potential weaknesses in ElGamal when a proposed
prime for DSA is used in ElGamal. That is what I was alluding to.
Again this is a good example of something positive I try to contribute
getting knocked down by some "elitez" poster using a pseudonym. At
least I got enough balls to post with my real name.
Oh, but *I'm* the bad little stupid boy....
Tom
Paul Rubin
> Sorry I meant to write "attacks like those on older implementations of DSA".
>
> I'm well aware of how DSA works.
I think you mean DH, not DSA.
Btw, finding a random 1024 bit p=2q+1 (p,q prime) took about 30 minutes
on my p3-750 using GMP in the totally obvious way.
Michael Scott
"Paul Rubin" <phr-n...@nightsong.com> wrote in message
news:7xd7317...@ruckus.brouhaha.com...
The totally obvious way is definitely not the best way. Both p and q should
be checked for small divisors before embarking on more expensive primality
tests. Using MIRACL on my p3-1000 it took about 45 seconds.
Mike Scott
Tom St Denis
I seriously doubt that. The density of such primes at around N=2^1024
is very low. Even for 512-bit primes you have to test a few thousand
candidates.
If you're claim is true then you will have no problem providing a list
of 3,500 such 1024-bit primes by sunday morning.
Tom
Paul Rubin
> I seriously doubt that. The density of such primes at around N=2^1024
> is very low. Even for 512-bit primes you have to test a few thousand
> candidates.
What do you expect the density to be, around N=2^1024?
Mike and I know the answer to this question, but I'm wondering whether
you do.
Tom St Denis
Well on a positive note your idea is a very good one. It speeds up the
search considerably. It still doesn't take 45 seconds :-)
Sorry for being a bit rude in my previous reply.
Tom
Tom St Denis
Of primes? about ln(x). Of these double primes? I dunno. With
256-bit primes of this sort the density is around 1/50 to 1/75.
I would imagine that the density for 1024-bit primes to be around 1/300
or so at the most.
Still, I've ran the modified sieve and it doesn't take 45 seconds.
Tom
Paul Rubin
> Of primes? about ln(x). Of these double primes? I dunno. With
> 256-bit primes of this sort the density is around 1/50 to 1/75.
>
> I would imagine that the density for 1024-bit primes to be around
> 1/300 or so at the most.
Why imagine? Why not calculate it? Assume the distribution of primes
in an interval around 2**1024 is more or less random with that
density.
> Still, I've ran the modified sieve and it doesn't take 45 seconds.
How do you know you did it the same way?
Tom St Denis
> Tom St Denis <tomst...@yahoo.com> writes:
>
>>Of primes? about ln(x). Of these double primes? I dunno. With
>>256-bit primes of this sort the density is around 1/50 to 1/75.
>>
>>I would imagine that the density for 1024-bit primes to be around
>>1/300 or so at the most.
>>
>
> Why imagine? Why not calculate it? Assume the distribution of primes
> in an interval around 2**1024 is more or less random with that
> density.
Well the prime density is about 1/709 using 1/lnx. Note that my
previous estimate was "1/300 primes" not "1/300 numbers".
>>Still, I've ran the modified sieve and it doesn't take 45 seconds.
>>
>
> How do you know you did it the same way?
Well his suggestion was to "do trial division on p and (p-1)/2" before
doing RM tests. I did that too. Obviously I didn't use MIRACL though I
can't imagine it would be that much faster than MPI [we're talking
orders of magnitude faster]
Tom
Paul Rubin
> Well the prime density is about 1/709 using 1/lnx. Note that my
> previous estimate was "1/300 primes" not "1/300 numbers".
How did you come up with that estimate? How long do you think MIRACL
should take, using Mike's method, if your estimate is correct? Assume
MIRACL on Mike's hardware can do around 50 1024-bit full width modexps
per second (50/sec an extrapolation from some other figures I've seen,
but probably isn't too far off) and that you can do trial division up
to say d=100 for "free" compared to a modexp. Do you think those
assumptions are unreasonable?
I'm not trying to give you a hard time, just trying to encourage you
to make a more careful mathematical estimate of the running speed. By
my calculation, Mike got a little bit lucky finishing in 45 seconds,
but the average case isn't too much worse than that.
> Well his suggestion was to "do trial division on p and (p-1)/2" before
> doing RM tests. I did that too. Obviously I didn't use MIRACL though
> I can't imagine it would be that much faster than MPI [we're talking
> orders of magnitude faster]
I don't know how fast MPI is, but if it's written in straightforward
C, it wouldn't surprise me if MIRACL is 10x faster.
Tom St Denis
> Tom St Denis <tomst...@yahoo.com> writes:
>
>>Well the prime density is about 1/709 using 1/lnx. Note that my
>>previous estimate was "1/300 primes" not "1/300 numbers".
>>
>
> How did you come up with that estimate? How long do you think MIRACL
> should take, using Mike's method, if your estimate is correct? Assume
> MIRACL on Mike's hardware can do around 50 1024-bit full width modexps
> per second (50/sec an extrapolation from some other figures I've seen,
> but probably isn't too far off) and that you can do trial division up
> to say d=100 for "free" compared to a modexp. Do you think those
> assumptions are unreasonable?
>
> I'm not trying to give you a hard time, just trying to encourage you
> to make a more careful mathematical estimate of the running speed. By
> my calculation, Mike got a little bit lucky finishing in 45 seconds,
> but the average case isn't too much worse than that.
Ok what part of
***IM RUNNING A TEST ON MY PC RIGHT NOW****
Don't you get?
>>Well his suggestion was to "do trial division on p and (p-1)/2" before
>>doing RM tests. I did that too. Obviously I didn't use MIRACL though
>>I can't imagine it would be that much faster than MPI [we're talking
>>orders of magnitude faster]
>>
>
> I don't know how fast MPI is, but if it's written in straightforward
> C, it wouldn't surprise me if MIRACL is 10x faster.
I doubt that. I would bet MPI is at most 2 times slower.
Even still I want my 3,500 primes by sunday morning.
Tom
Michael Scott
Actually I was more than a bit lucky with the first few.
But here's 60+ in the meantime. 3440 to follow.
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139534
02127
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139540
16587
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139540
58659
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139541
86087
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139550
20423
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139551
95479
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139552
20547
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139570
81843
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139578
90463
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139585
91563
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139597
17547
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139604
65723
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139615
28803
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139623
69883
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139626
09739
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139629
43567
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139634
93059
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139635
86299
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139640
62399
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139654
93339
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139662
84199
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139670
85439
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139684
81003
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139687
70599
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139691
82583
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139697
24419
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139700
42659
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139705
79419
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139714
00687
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139716
81487
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139726
76863
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139729
02847
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139729
77247
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139737
46723
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139741
39459
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139747
29907
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139752
91687
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139756
48339
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139761
09967
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139766
00119
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139766
73139
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139775
36539
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139792
67407
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139796
30623
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139799
00083
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139804
88263
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139805
63059
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139817
04823
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139835
10739
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139842
27907
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139861
54747
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139865
24587
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139868
32543
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139877
89039
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139878
40939
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139887
94903
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139903
38559
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139904
87239
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139914
89479
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139915
11847
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139928
93767
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139932
30487
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139934
88727
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139940
29579
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139949
10307
1277941319242747935947317754447952016162192896099132751456246855099196472156
0178335120542817920310489306715768836506463424165011629640631424909598346041
1036257068627301999533205225648344228991688528838623096645303354445244025151
5057128211852519802588522306412059837966182336110991608938777279974798139959
15103
Mike Scott
"Tom St Denis" <tomst...@yahoo.com> wrote in message
news:3BE34190...@yahoo.com...
Tom St Denis
> Actually I was more than a bit lucky with the first few.
>
> But here's 60+ in the meantime. 3440 to follow.
Question: How many #'s are you testing per second? MPI [at idle
priority] gets 324, 1024-bit numbers per second on my 1.2ghz Athlon.
I've got a feeling I put my feet in my mouth....
Tom
Paul Rubin
> priority] gets 324, 1024-bit numbers per second on my 1.2ghz Athlon.
>
> I've got a feeling I put my feet in my mouth....
I think Mike's algorithm is something like this:
1. Generate random 1024 bit p. Set q = (p-1)/2.
2. Check p and q for small prime divisors, up to d=100, say.
If either has a small divisor, discard both and go back to step 1.
3. Do a full primality test on q; if it fails, discard p and q
and go back to step 1.
4. Do full primality test on p. If it passes, you've finished.
Otherwise, discard p and q and go back to step 1.
Your assignment: analyze this algorithm (estimate the number of times
each step is executed and how long each one takes). Good luck Jim ;-).
P.S. Extra credit: you might like to begin step 2 by first testing
up to d=23. Why?
Corners
I don't think you're stupid. And I appreciate your positive
contributions here. It looks like you were treated rudely.
I would have said "unfairly", except for some of your own
recent posts. It looks like some bad Karma came back home.
A little patience, a little humility, a little more good
will could benefit us all.
***
corners
who's reasons for posting under a pseudonym are not related
to testicular deficiency.
Roger Schlafly
> I think Mike's algorithm is something like this:
> 1. Generate random 1024 bit p. Set q = (p-1)/2.
> 2. Check p and q for small prime divisors, up to d=100, say.
> If either has a small divisor, discard both and go back to step 1.
> 3. Do a full primality test on q; if it fails, discard p and q
> and go back to step 1.
> 4. Do full primality test on p. If it passes, you've finished.
> Otherwise, discard p and q and go back to step 1.
Ok, but if you really want to generate a lot of these fast, then
you could choose DSA primes where q << p. Then step 3
is fast, and the whole thing is much faster.
Tom St Denis
> Tom St Denis <tomst...@yahoo.com> writes:
>
>>Question: How many #'s are you testing per second? MPI [at idle
>>priority] gets 324, 1024-bit numbers per second on my 1.2ghz Athlon.
>>
>>I've got a feeling I put my feet in my mouth....
>>
>
> I think Mike's algorithm is something like this:
>
> 1. Generate random 1024 bit p. Set q = (p-1)/2.
> 2. Check p and q for small prime divisors, up to d=100, say.
> If either has a small divisor, discard both and go back to step 1.
> 3. Do a full primality test on q; if it fails, discard p and q
> and go back to step 1.
> 4. Do full primality test on p. If it passes, you've finished.
> Otherwise, discard p and q and go back to step 1.
I'm using the same algorithm actually, just different bignum lib.
> Your assignment: analyze this algorithm (estimate the number of times
> each step is executed and how long each one takes). Good luck Jim ;-).
Well step #1-#4 are going to be executed at most asymtoptically (lnx)^2
times since the goal is to find two primes at the same time. If you
check all the primes upto N you filter out 1.2/lnN of all composites
[according to AC2]. So X=2^1024 then (lnX)^2 = 503791. Since we are
filtering twice with the primes a binomial is required, namely
2*[(1.2/lnN)(1-1.2/lnN)] + (1.2/lnN)^2
Which for N=256 is 61% [if I got it right]. 61% of 503791 is 309338.
So step #1 and #2 are executed 309338 times and #3-4 executed 194453
times at most on average.
Tom
Tom St Denis
The whole point is not to make DSA primes. I want to make primes where
the smallest sub-group [non trivial] is huge.
Tom
Tom St Denis
> Well step #1-#4 are going to be executed at most asymtoptically (lnx)^2
> times since the goal is to find two primes at the same time. If you
> check all the primes upto N you filter out 1.2/lnN of all composites
> [according to AC2]. So X=2^1024 then (lnX)^2 = 503791. Since we are
> filtering twice with the primes a binomial is required, namely
>
> 2*[(1.2/lnN)(1-1.2/lnN)] + (1.2/lnN)^2
>
> Which for N=256 is 61% [if I got it right]. 61% of 503791 is 309338.
When I actually run the test the sieve [divide by primes] takes out
98.43% of all candidates. So my estimate was far off.
Tom
M.S. Bob
>
> > I don't know how fast MPI is, but if it's written in straightforward
> > C, it wouldn't surprise me if MIRACL is 10x faster.
>
> I doubt that. I would bet MPI is at most 2 times slower.
GMP is between 5 - 10 times faster than MPI in my experiences relating
to just looking for 1024-bit primes (using MR testing) if I remember
correctly. So MIRACL being 10x faster is very possible.
Tom St Denis
> Well step #1-#4 are going to be executed at most asymtoptically (lnx)^2
> times since the goal is to find two primes at the same time. If you
> check all the primes upto N you filter out 1.2/lnN of all composites
> [according to AC2]. So X=2^1024 then (lnX)^2 = 503791. Since we are
> filtering twice with the primes a binomial is required, namely
>
> 2*[(1.2/lnN)(1-1.2/lnN)] + (1.2/lnN)^2
>
> Which for N=256 is 61% [if I got it right]. 61% of 503791 is 309338.
Oops... if I plug in
q = 1 - (1.2/lnN);
L = 2*(q*(1-q)) + q^2
Then L is very close to the desired value of 98%.
So there!
:-)
Tom
Tom St Denis
Arrg... posting too quickly... I used N=1619 in my program...
Tom
Mike Scott
You're welcome
> Sorry for being a bit rude in my previous reply.
>
No harm done.
Mike Scott
> Tom
>
Paul Rubin
> Well step #1-#4 are going to be executed at most asymtoptically
> (lnx)^2 times since the goal is to find two primes at the same time.
> If you check all the primes upto N you filter out 1.2/lnN of all
> composites [according to AC2].
What exactly do you mean about 1.2/lnN? If I have a random composite
and test it by trial division up to N=100, what's the probability of
the test succeeding (i.e. the probability of finding such a divisor)?
Are you saying it's 1.2/ln(100) = 26%? That can't possibly be right.
If I test only up to N=2, i.e. the only test I do is throw away
even numbers, that gets rid of 50% right there.
> So X=2^1024 then (lnX)^2 = 503791.
OK
> Since we are filtering twice with the primes a binomial is required,
> namely
>
> 2*[(1.2/lnN)(1-1.2/lnN)] + (1.2/lnN)^2
>
> Which for N=256 is 61% [if I got it right]. 61% of 503791 is 309338.
>
> So step #1 and #2 are executed 309338 times and #3-4 executed 194453
> times at most on average.
This part, I don't understand.
Tom St Denis
> Tom St Denis <tomst...@yahoo.com> writes:
>
>>Well step #1-#4 are going to be executed at most asymtoptically
>>(lnx)^2 times since the goal is to find two primes at the same time.
>>If you check all the primes upto N you filter out 1.2/lnN of all
>>composites [according to AC2].
>>
>
> What exactly do you mean about 1.2/lnN? If I have a random composite
> and test it by trial division up to N=100, what's the probability of
> the test succeeding (i.e. the probability of finding such a divisor)?
> Are you saying it's 1.2/ln(100) = 26%? That can't possibly be right.
> If I test only up to N=2, i.e. the only test I do is throw away
> even numbers, that gets rid of 50% right there.
It's "1 - 1.2/lnN" so if you divide all primes upto 256 you eliminate
78% of random composites.
>> So X=2^1024 then (lnX)^2 = 503791.
>>
>
> OK
>
>
>>Since we are filtering twice with the primes a binomial is required,
>>namely
>>
>>2*[(1.2/lnN)(1-1.2/lnN)] + (1.2/lnN)^2
>>
>>Which for N=256 is 61% [if I got it right]. 61% of 503791 is 309338.
>>
>>So step #1 and #2 are executed 309338 times and #3-4 executed 194453
>>times at most on average.
>>
>
> This part, I don't understand.
I got it backwards, it was
q = 1 - 1.2/lnN
L = 2(q)(1-q) + q^2
And I've verified this with my program, its true :-)
Tom
Paul Rubin
> It's "1 - 1.2/lnN" so if you divide all primes upto 256 you eliminate
> 78% of random composites.
Hmm, do you know where that formula comes from? It still doesn't sound
right to me:
1) start with random composite
2) check for divisibility by 2. That eliminates 50%.
3) check for divisibility by 3. That eliminates 33% of what's left.
4) check for divisibility by 5. That eliminates 20% of what's left.
5) check for divisibility by 7. That eliminates 14% of what's left.
50%*(1-33%)*(1-20%)*(1-14%) = 23% approx.
So 77% are already gone just by testing up to N=7. Is something wrong
with this logic?
Tom St Denis
> Tom St Denis <tomst...@yahoo.com> writes:
>
>>It's "1 - 1.2/lnN" so if you divide all primes upto 256 you eliminate
>>78% of random composites.
>>
>
> Hmm, do you know where that formula comes from? It still doesn't sound
> right to me:
> 1) start with random composite
> 2) check for divisibility by 2. That eliminates 50%.
> 3) check for divisibility by 3. That eliminates 33% of what's left.
Not true. 1/6 of all numbers are divisible by both. So thats
1/2 + 1/3 - 1/6 = 66%
> 4) check for divisibility by 5. That eliminates 20% of what's left.
> 5) check for divisibility by 7. That eliminates 14% of what's left.
>
> 50%*(1-33%)*(1-20%)*(1-14%) = 23% approx.
>
> So 77% are already gone just by testing up to N=7. Is something wrong
> with this logic?
Note that 1/lnx and 1.2/lnx apply for larger values of x, it doesn't
work well for small values like 3 or 7.
Note that the previous formulas that I editted are correct since I've
verified them by running the sieve program and counting how many
candidates each phase rejects.
Tom
Paul Rubin
> > 2) check for divisibility by 2. That eliminates 50%.
> > 3) check for divisibility by 3. That eliminates 33% of what's left.
>
>
> Not true. 1/6 of all numbers are divisible by both. So thats
>
> 1/2 + 1/3 - 1/6 = 66%
Yes, that works out the same way. Eliminate 50%. 1/3 of what's left
is 1/6 of what you started with. 1/2 + 1/6 = 2/3.
Tom St Denis
Eitherway, 1.2/lnN works well as N grows [taken from AC2]
Tom
Paul Rubin
> Eitherway, 1.2/lnN works well as N grows [taken from AC2]
It still doesn't sound right. For N=1000, 1.2/ln(N)=17.37%, but
multiplying out (1-1/2)*(1-1/3)*...*(1-1/997) gives 8.1%.
Tom St Denis
What are you talking about?
Go out and read page 260 of Applied Crypto 2nd Edition.
Tom
Bryan Olson
Paul Rubin wrote:
> I think Mike's algorithm is something like this:
>
> 1. Generate random 1024 bit p. Set q = (p-1)/2.
> 2. Check p and q for small prime divisors, up to d=100, say.
> If either has a small divisor, discard both and go back to step 1.
> 3. Do a full primality test on q; if it fails, discard p and q
> and go back to step 1.
> 4. Do full primality test on p. If it passes, you've finished.
> Otherwise, discard p and q and go back to step 1.
Doing a "full primality test" in step 3 will make the algorithm
significantly slower than it could be. Insert the following steps
between steps 2 and 3 above:
2.1. Do a single iteration of base-2 Fermat or Miller-Rabin test
on q. If it fails, go back to step 1.
2.2. Do a single iteration of base-2 Fermat or Miller-Rabin test
on p. If it fails, go back to step 1.
--Bryan
Paul Rubin
> Doing a "full primality test" in step 3 will make the algorithm
> significantly slower than it could be. Insert the following steps
> between steps 2 and 3 above:
>
> 2.1. Do a single iteration of base-2 Fermat or Miller-Rabin test
> on q. If it fails, go back to step 1.
>
> 2.2. Do a single iteration of base-2 Fermat or Miller-Rabin test
> on p. If it fails, go back to step 1.
Yes, ok. In practice, that's a full primality test anyway.
Incognito Innominatus
> I think Mike's algorithm is something like this:
>
> 1. Generate random 1024 bit p. Set q = (p-1)/2.
> 2. Check p and q for small prime divisors, up to d=100, say.
> If either has a small divisor, discard both and go back to step 1.
> 3. Do a full primality test on q; if it fails, discard p and q
> and go back to step 1.
> 4. Do full primality test on p. If it passes, you've finished.
A better algorithm is to use a sieve, or actually a double sieve.
You want to set up a sieve for values q which eliminates values for which
either q or 2q+1 are divisible by a small prime. This is a relatively
straightforward modification to the usual Sieve of Eratosthenes.
Where you are striking out multiples of small prime s, you also strike
out values which are (s-1)/2 mod s. Instead of advancing the pointer by
s units each time and striking out, you advance by (s-1)/2 and strike out,
then by (s+1)/2 and strike out. It is hardly any more complicated.
Another point is that you only need to work with q values which are 5
mod 12. No other value mod 12 can be such that both q and 2q+1 are prime.
Paul Rubin
> A better algorithm is to use a sieve, or actually a double sieve.
> You want to set up a sieve for values q which eliminates values for which
> either q or 2q+1 are divisible by a small prime. This is a relatively
> straightforward modification to the usual Sieve of Eratosthenes.
> Where you are striking out multiples of small prime s, you also strike
> out values which are (s-1)/2 mod s. Instead of advancing the pointer by
> s units each time and striking out, you advance by (s-1)/2 and strike out,
> then by (s+1)/2 and strike out. It is hardly any more complicated.
It's not obvious to me how to do this and still hit the different primes
with equal probability. What do you have in mind?
Anyway, in that algorithm description I took the attitude that testing
for small divisors was "free" compared to a Fermat test.
> Another point is that you only need to work with q values which are 5
> mod 12. No other value mod 12 can be such that both q and 2q+1 are prime.
Hmm, yes, it might give a slight speedup to examine q%12 first (or
something equivalent), not to save some small divisor tests, but
because it will occasionally save a Fermat test on p.
Roger Schlafly
> Another point is that you only need to work with q values which are 5
> mod 12. No other value mod 12 can be such that both q and 2q+1 are prime.
Or 11 mod 12. Eg, 11 and 23 are prime. 23 and 47 are prime.
I reiterate that for most cryptographic purposes, it is better to
choose q << p, and then none of the problems of this thread arise.
Tom St Denis
I'd rather not have small sub-groups. That's where all the problems
arise, when you play on the edge.
Recall that 512-bit RSA was secure once too :-)
I'd much rather use a 1024-bit DH key where the smallest nontrivial
group has an order of ~2^1022 than one where the smallest group has an
order of ~2^160.
Tom
Paul Rubin
> I reiterate that for most cryptographic purposes, it is better to
> choose q << p, and then none of the problems of this thread arise.
Are there reasons to think there's no attacks on the q subgroup better
than the rho method?
Roger Schlafly
These opinions are based on best knowledge, not proofs. I can
only refer you to the experts.
NIST says that 1024-bit DH only needs a 160-bit subgroup.
http://csrc.nist.gov/encryption/kms/key-management-guideline-(workshop).pdf
Lenstra-Verheul say that 1028-bit DH only needs a 127-bit subgroup.
http://www.cryptosavvy.com/table.htm
Tom St Denis
Tom says he wants big sub-groups because he doesn't care about signing
or encrypting 105msec faster :-)
Tom
Paul Crowley
> I think Mike's algorithm is something like this:
>
> 1. Generate random 1024 bit p. Set q = (p-1)/2.
> 2. Check p and q for small prime divisors, up to d=100, say.
> If either has a small divisor, discard both and go back to step 1.
> 3. Do a full primality test on q; if it fails, discard p and q
> and go back to step 1.
You can speed these three steps up more than somewhat by using a real
sieve. This may not seem worth it, but the advantage is you can use a
much higher d_max, which can save on full primality tests. For RSA
prime finding I estimated that it's worth testing up to d=65537 or
so. For these primes it might be worth going even higher; I haven't
done the math.
> 4. Do full primality test on p. If it passes, you've finished.
> Otherwise, discard p and q and go back to step 1.
--
__ Paul Crowley
\/ o\ s...@paul.cluefactory.org.uk
/\__/ http://www.cluefactory.org.uk/paul/
"Conservation of angular momentum makes the world go around" - John Clark
Tom St Denis
> Paul Rubin <phr-n...@nightsong.com> writes:
>
>>I think Mike's algorithm is something like this:
>>
>> 1. Generate random 1024 bit p. Set q = (p-1)/2.
>> 2. Check p and q for small prime divisors, up to d=100, say.
>> If either has a small divisor, discard both and go back to step 1.
>> 3. Do a full primality test on q; if it fails, discard p and q
>> and go back to step 1.
>>
>
> You can speed these three steps up more than somewhat by using a real
> sieve. This may not seem worth it, but the advantage is you can use a
> much higher d_max, which can save on full primality tests. For RSA
> prime finding I estimated that it's worth testing up to d=65537 or
> so. For these primes it might be worth going even higher; I haven't
> done the math.
You're kidding right? With d=1619 [first 256 primes] I can find 768 bit
primes in under 5 seconds, and 1024-bit primes in under 15 seconds using
MPI. Those are not bad speeds.
Recall that the sieve step efficiency goes up logratihmically and the
work linearly. So there is a breaking point where you spend more time
then it actually saves. e.g. sieve upto d=251 and do one round of MR
will get rid of more composites faster than with d=65537.
Tom
Bryan Olson
> Paul Crowley wrote:
>
> >
> >>I think Mike's algorithm is something like this:
> >>
> >> 1. Generate random 1024 bit p. Set q = (p-1)/2.
> >> 2. Check p and q for small prime divisors, up to d=100, say.
> >> If either has a small divisor, discard both and go back to step 1.
> >> 3. Do a full primality test on q; if it fails, discard p and q
> >> and go back to step 1.
> >>
> >
> > You can speed these three steps up more than somewhat by using a real
> > sieve. This may not seem worth it, but the advantage is you can use a
> > much higher d_max, which can save on full primality tests. For RSA
> > prime finding I estimated that it's worth testing up to d=65537 or
> > so. For these primes it might be worth going even higher; I haven't
> > done the math.
>
>
> You're kidding right?
He's quite serious. At d=65537 the sieve step will still take a trivial
fraction of the time.
> With d=1619 [first 256 primes] I can find 768 bit
> primes in under 5 seconds, and 1024-bit primes in under 15 seconds using
> MPI. Those are not bad speeds.
>
> Recall that the sieve step efficiency goes up logratihmically and the
> work linearly.
That's wrong; the work does not go up linearly in the number of primes.
Removing the multiples of large primes from the sieve bitmap is much
faster than removing the multiples of small primes.
Even using trial division, the increase is not linear. We only test for
divisibility by large primes when a number passes the test for all the
smaller primes.
> So there is a breaking point where you spend more time
> then it actually saves. e.g. sieve upto d=251 and do one round of MR
> will get rid of more composites faster than with d=65537.
You didn't test it did you? The small prime limit is not a sensitive
parameter. A wide range is negligibly far from optimal. Nevertheless,
Paul Rubin's suggested limit does seem to small.
--Bryan
Tom St Denis
Actually thats all wrong. Dividing by a prime p removes 1/p numbers.
So as you divide by ever increasing primes the likelyhood that a random
number is a multiple of it is low.
For example, suppose you have a 100-digit prime. The likelyhood that a
150 digit random number is a multiple of that prime is 10^-100, an
amazingly small prob.
Likewise, as you sieve with a base of ever increasing size the gain [i.e
succesful detection of composite] increases slower and slower.
The approximate probability that a number is not a multiple of any prime
less than N is 1.12/ln N [taken from AC2, and verified empiracly].
>>So there is a breaking point where you spend more time
>>then it actually saves. e.g. sieve upto d=251 and do one round of MR
>>will get rid of more composites faster than with d=65537.
>>
>
> You didn't test it did you? The small prime limit is not a sensitive
> parameter. A wide range is negligibly far from optimal. Nevertheless,
> Paul Rubin's suggested limit does seem to small.
Now you've got to be kidding too. ...
Tom
Paul Rubin
> > So there is a breaking point where you spend more time
> > then it actually saves. e.g. sieve upto d=251 and do one round of MR
> > will get rid of more composites faster than with d=65537.
>
> You didn't test it did you? The small prime limit is not a sensitive
> parameter. A wide range is negligibly far from optimal. Nevertheless,
> Paul Rubin's suggested limit does seem to small.
Fair enough. d=100 lets about 12% of numbers through. d=65536 lets
through about 5%. Since you're filtering twice, it means you're
doing (12/5)**2 or almost 6x fewer full tests. Using a sieve does
make coding the algorithm more complicated, and is only worthwhile
if you want a lot of these primes.
In my situation, I only wanted one, so coded the obvious way (full
test on p before examining q) and it took 1/2 hour or so to run.
That's why this thread interested me--I'd overlooked that doing small
divisor tests on both p and q before doing any full tests could have
gotten it to under 1 minute, meaning an extra minute or two spent
coding would have gotten my answer sooner. If I spent 1/2 hour
coding and debugging a sieve to just run it once, I come out behind ;-).
Bryan Olson
> It's "1 - 1.2/lnN" so if you divide all primes upto 256 you eliminate
> 78% of random composites.
That's not what AC2 says. The formula is for the fraction of *odd*
candidates. See page 261.
Paul Rubin is right.
--Bryan
Bryan Olson
> Actually thats all wrong. Dividing by a prime p removes 1/p numbers.
> So as you divide by ever increasing primes the likelyhood that a random
> number is a multiple of it is low.
Right, I didn't disagree with that, but Tom's analysis on it is still
wrong because he didn't actually do the computation with the numbers at
issue.
> For example, suppose you have a 100-digit prime. The likelyhood that a
> 150 digit random number is a multiple of that prime is 10^-100, an
> amazingly small prob.
Why not use the real numbers? Paul Rubin suggested going up to 100, and
Paul Crowley claimed that if using a sieve, 65537 would be better. Tom
followed with the "are you kidding" remark, and stated he uses a max of
1619.
Let's do some math. When we filter out multiples of small primes, the
time is spent in dividing a large numbers by single-word quantities,
which is linear time in the length of the large numbers. We save time
by doing fewer modular exponentiations. Multiplying two large numbers
is (using the methods of the crypto libraries) quadratic time. On a
typical 32-bit machine, modular multiplication or squaring of two
1024-bit numbers takes somewhere between 32 and 64 times as long as
computing the remainder of a 1024-bit number divided by a
single-precision quantity; let's say about 40 times. The modular
exponentiation might use multi-bit scanning, and call for maybe 1200
such multiplies.
Thus the modular exponentiation is about 50,000 times as expensive as
the trial division by a single-word prime. If we're looking for a
single prime, and are filtering by direct trial division, we should test
against primes up to about 50,000, since at that point we are spending
one unit of time for a 1/50,000 chance of saving 50,000 units of time.
That's the break-even point.
Use of the sieve (or offset-table) changes things. We only have to
compute the small-prime remainder once, and we have a chance to save a
modular exponentiation for every candidate we test. Thus we should use
more small primes, since the chance of any given prime saving a modular
exponentiation goes up.
> Likewise, as you sieve with a base of ever increasing size the gain [i.e
> succesful detection of composite] increases slower and slower.
>
> The approximate probability that a number is not a multiple of any prime
> less than N is 1.12/ln N [taken from AC2, and verified empiracly].
No, that figure is for odd integers. How Tom verified it is a mystery.
(Also the numbers must be qualified as "randomly chosen".)
> >>So there is a breaking point where you spend more time
> >>then it actually saves. e.g. sieve upto d=251 and do one round of MR
> >>will get rid of more composites faster than with d=65537.
Let's do some more math. If we sieve up to a max of 65536, then the
chance of randomly chosen integer passing the sieve step is about 0.05.
The density of 1024-bit primes is about 1/700. Thus the expected number
of candidates we'll have to MR-test is about 35. (For now I'm assuming
we're looking for general primes, not Sophie Germain primes.)
So is 65537 too large? As before, if it costs us one unit of time to
include one prime in the sieve, then a Miller-Rabin test costs us about
50,000 units. The prime 65537 has a 1/65537 chance of saving 50,000
units on each of the 35 expected trials. It saves an average of about
27 units at a cost of one unit.
Thus we see that d=65536 is sub-optimal because it is too *small*.
The subject of the thread is generation of Sophie Germain primes.
Compared to general primes, it increases the number of expected trials,
and justifies an even larger sieving range.
[Bryan:]
> > You didn't test it did you? The small prime limit is not a sensitive
> > parameter. A wide range is negligibly far from optimal. Nevertheless,
> > Paul Rubin's suggested limit does seem to small.
>
>
> Now you've got to be kidding too. ...
Nope. Paul Rubin's suggestion was too small. Tom's was too small, but
I'd expect it to perform reasonably well. Even Paul Crowley's is too
small for optimal time, but I'd expect the difference to be lost in the
noise.
--Bryan
Benjamin Goldberg
> > priority] gets 324, 1024-bit numbers per second on my 1.2ghz Athlon.
> >
> > I've got a feeling I put my feet in my mouth....
>
> I think Mike's algorithm is something like this:
>
> 1. Generate random 1024 bit p. Set q = (p-1)/2.
> 2. Check p and q for small prime divisors, up to d=100, say.
> If either has a small divisor, discard both and go back to
> step 1.
> 3. Do a full primality test on q; if it fails, discard p and q
> and go back to step 1.
>
> Your assignment: analyze this algorithm (estimate the number of times
> each step is executed and how long each one takes). Good luck
> Jim ;-).
>
> P.S. Extra credit: you might like to begin step 2 by first testing
> up to d=23. Why?
Because you could multiply together all small primes up to d=23, then
find the gcd of that and your candidate. The gcd step will be fewer
operations than the x many trial divisions for primes up to 23 would be.
d is chosen as 23 because the product is a 28 bit number. If you did up
to d=29, then the product would be a 33 bit number, which wouldn't fit
in a single word.
Some other possible speedups:
It might be of benefit to combine steps 3 and 4. Instead of doing all
your rounds of Rabin-Miller on q, then all your rounds on p, alternate
between doing one round on q, then one round on p. Suppose each "full
primality test" is 64 rounds of Rabin-Miller, and consider the case when
q is prime, but p isn't: in the uncombined version, you would have to do
64 rounds on q before moving on to p; in the combined version, we will
hopefully dectect p's compositness before we have done 64 rounds total.
This also applies to doing trial division on each -- instead of looking
at p, with each divisor, then q, with each divisor, loop through your
divisors, and for each one, first test p against it, then q.
--
Klein bottle for rent - inquire within.
Paul Rubin
> It might be of benefit to combine steps 3 and 4. Instead of doing all
> your rounds of Rabin-Miller on q, then all your rounds on p, alternate
> between doing one round on q, then one round on p. Suppose each "full
> primality test" is 64 rounds of Rabin-Miller, and consider the case when
> q is prime, but p isn't: in the uncombined version, you would have to do
> 64 rounds on q before moving on to p; in the combined version, we will
> hopefully dectect p's compositness before we have done 64 rounds total.
Yes, I was going with the idea that a full test is one round. If p
and q both pass one round, declare the algorithm finished, then do
additional rounds to make completely sure, but alert the Weekly World
News if any of the additional rounds fail.
> This also applies to doing trial division on each -- instead of looking
> at p, with each divisor, then q, with each divisor, loop through your
> divisors, and for each one, first test p against it, then q.
I'm going with the idea that the small-d trial divisions are basically
free, but otherwise yes, this is good.
Michael J. Fromberger
>> Well his suggestion was to "do trial division on p and (p-1)/2"
>> before doing RM tests. I did that too. Obviously I didn't use
>> MIRACL though I can't imagine it would be that much faster than MPI
>> [we're talking orders of magnitude faster]
>I don't know how fast MPI is, but if it's written in straightforward
>C, it wouldn't surprise me if MIRACL is 10x faster.
It is written in straightforward C, and I would not at all be
surprised to find MIRACL to be that much faster, although I have not
done any timing comparisons on the two. I wrote MPI to be small,
simple, self-contained, and portable (and also to have the experience
of doing it). "Fast" was not one of my main design goals.
Cheers,
-M
--
Michael J. Fromberger Software Engineer, Thayer School of Engineering
sting <at> linguist.dartmouth.edu http://www.dartmouth.edu/~sting/
"One must learn by doing the thing; for though you think you know it, you
have no certainty 'til you try." -- Sophocles
Bryan Olson
Paul Rubin wrote (about Miller-Rabin testing):
> Yes, I was going with the idea that a full test is one round. If p
> and q both pass one round, declare the algorithm finished, then do
> additional rounds to make completely sure, but alert the Weekly World
> News if any of the additional rounds fail.
A couple points that I find interesting...
Mark Wooding, whom I have never met but trust based on his posts here,
reported that he once encountered a pseudo-prime in practice (posts of
2001-07-06 and 2001-09-04). It was a Fermat test rather than a
Miller-Rabin, but that's not a huge difference.
I have been too lazy to look up and/or work out the odds of the
long-shot Wooding hit.
Second point: Unless I make a mistake in the logic below, a single
base-2 Fermat test is perfect for p (the larger of the two in the
notation here; we're using = 2q + 1). The single test proves that if q
is prime, then p is prime.
Theorem: If q is prime, and
2^2q mod (2q+1) = 1,
then 2q+1 is prime.
Proof: Since 2^2q mod (2q+1) = 1, the order of 2 in the multiplicative
group modulo p = 2q + 1 must divide 2q. Since q is prime, the only
divisors are 1, 2, q and 2q. The order of 2 cannot be 1 or 2, since p
must be at least 5. Thus the order has a factor of q. The order of an
element must divide the order of the group, so the order of the
multiplicative group mod p must be a multiple of q. It also must be a
multiple of 2, since p-1 has order 2. Thus the order of the group must
have a factor of 2q (even if q=2 since it's true for p=5). The order
cannot be larger than 2q, so it must be 2q which only happens if p is
prime.
Thus the additional rounds need only be applied to q, and not to p.
I'd guess the result is probably well-known, but it seemed interesting
enough to work out here. The optimization will save only a trivial
amount of time, since the final testing is cheap compared to finding p
and q that pass a one-round test.
--Bryan
Gregory G Rose
Bryan Olson <non...@nowhere.org> wrote:
>Mark Wooding, whom I have never met but trust based on his posts here,
>reported that he once encountered a pseudo-prime in practice (posts of
>2001-07-06 and 2001-09-04). It was a Fermat test rather than a
>Miller-Rabin, but that's not a huge difference.
I can also testify that, back in the late 80's
when we put a small Sequent to work generating
100-decimal-digit primes, I saw at least one
composite that passed a single Fermat test.
We eventually generated on the order of 100,000
primes before realising that of course no-one
would trust us to generate keys for them...
Greg.
--
Greg Rose INTERNET: g...@qualcomm.com
Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199
Level 3, 230 Victoria Road, http://people.qualcomm.com/ggr/
Gladesville NSW 2111 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C