Always after me lucky primes...

[Nathan Zook <nzook@bga.com>]

-----BEGIN PGP SIGNED MESSAGE-----
 
So Hal thinks that it would take a lot of work to get a private exponent
that is even marginally short?
 
Let n be the random number generated by keystrokes.
Let m be n mod (0x10001 * 8 * 9 * 25 * 49).
Let s be m mod 0x10001.
Let n1 be n + 0x10000 - s.  Let t be m + 0x10000 - s mod 8 * 9 * 25 * 49.
Let t2 be m mod 8, t3 be m mod 9, t5 be m mod 25, t7 be m mod 49.
Let n2 be n1 / 2, n3 be n1 / 3, n4 be n1 / 4, ... n7 be n1/7.
 
using t's, determine if n1 is a mult of 2, 3, 5, 7.
if so, check appropriate element of {n2, n3, n4, n5, n6, n7} for primeness.
(there may not be one).
if not check n1.
EndELSE
 
Loop:
Determine if some element of {n1,...n7} is prime 
If so, let d = (n1 + 1 ) / 0x10001
     [equiv: n1/0x10001 + 1]
  Let k = 0's in d.
     [check previous flamage for best method]
  If k is below threshhold, save and exit.
     (you may wish to ensure that k is _above_ a certain threshhold...)
EndIF
EndIF
 
Let n1 += 0x10001
using t's, determine if n1 is a mult of 2, 3, 5, 7. 
if so, increment the appropriate elements of {n2, ... n7}.
also, check appropriate element of {n2, n3, n4, n5, n6, n7} for primeness.
  (there may not be one).
if not check n1.
EndELSE
 
EndLoop:
 
:-D
Cypherpunks write algorithms, and argue about operating systems.
 
 
Clearly, if you wish to be a stickler about the number of digits that you
end up with, you wouldn't use n2 through n7.  The t's, however, or some
version thereof, would speed the checking noticably.
 
 
Nathan
 
I hearby provide notice of claim to all intelectual copyrights relating to
the above algorithm(s) against all entities using the algorithms for
commercial purposes, specifically against PKP, and Viacrypt, their
assignees, and anyone claiming the devolution of their patents. For non-
commerical use, including inclusion into PGP (tm) packages that will be
distributed free of charge, Fred Fish and similiar distributions, I release
all claims, providing a copy of this notice is included.
 
 
"PGP?"                        "ITAR!"                          "Oh, RKBA!"
 
 
                   |--------------------------------------------------+
  ----------------- 14712B4D 1994/12/26 Nathan H. Zook <nzook@bga.com> )
 |44B3D866 3D551E2E ---------------------------------------------------
 |F89222A6 338CDE24/ |
  -----------------
 
-----BEGIN PGP SIGNATURE-----
Version: 2.6.2
 
iQEVAwUBLyu1SHmgMs8UcStNAQGXjQgAmr0PN2RbLwM4IN15YdQhwD/IvYFylTCS
naRCyvqjgzdsPROZAhZKP5eoVbMn6xWmwRhxfplGTCKf3YMRu9FSQHEc7ekL7QQw
mxRvGC2WOMkMuIRXt0DKu6keof9XwWUL2voni+eKme50sppf0ETmLu1outjcCyR6
bJD0XyUxbBPUKpP4prQSc/kT7XVt+wGJVRZtkN1F+43roLRLZYzzjItuR4gqUQ8D
WpC8CDfQTCLb0GDKNC+ZirNdSKGg2t3XnHC2gQpXRLRykPlYG9SpBDm+VuIXV0vl
dALZLV9UtNyulmOYqqkCqBmAavDQDuTjbRnELLsELLSSZrOIiKQ+Sw==
=CaQ6
-----END PGP SIGNATURE-----