Computer graphics processing and selective visual display system – Plural physical display element control system – Segmented display elements
Reexamination Certificate
1999-12-30
2003-08-05
Hjerpe, Richard (Department: 2674)
Computer graphics processing and selective visual display system
Plural physical display element control system
Segmented display elements
C345S030000, C345S044000, C345S046000, C315S24100S, C250S201100, C250S201900, C250S586000, C257S139000, C257S141000, C257S141000, C257S141000
Reexamination Certificate
active
06603445
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of Invention
The present invention relates to a method and apparatus for factoring large numbers with optoelectronic devices.
2. Description of the Prior Art
The security of the RSA public key cryptosystem depends on the difficulty of factoring a large number n which is the product of two equal size primes p and q. This problem had been thoroughly investigated (especially over the last 25 years), and the last two breakthroughs were the development of the Quadratic Sieve (QS) algorithm, see C. Pomerance, The quadratic sieve factoring algorithm, Proceedings of EUROCRYPT 84 (LNCS 209), 169-182, 1985, and the development of the Number Field Sieve (NFS) algorithm, see A. K. Lenstra, H. W. Lenstra, M. S. Manasse, and J. M. Pollard, The number field sieve, Vol. 1554 of Lecture Notes in Mathematics, 11-42, Springer Verlag, 1993. The asymptotic time complexity of the QS algorithm and the asymptotic time complexity of the NFS algorithm are different. For numbers with up to about 350 bits the QS algorithm is faster due to its simplicity, but for larger numbers the NFS algorithm is faster due to its better asymptotic complexity.
The complexity of the NFS algorithm grows fairly slowly with the binary size of n. The current record in factoring large RSA keys is the factorization of a 512 bit number achieved in August 1999 by running the Number Field Sieve on several hundred workstations for several months. If we denote by X the (barely possible) complexity of factoring a 512 bit number, the complexity of factoring numbers which are 100 bits longer is about 40X, the complexity of factoring numbers with are 150 bits longer is about 220X, and the complexity of factoring numbers which are 200 bits longer is about 1100X. Accordingly, the main problem confronting researchers in this field is to improve the efficiency of factoring.
SUMMARY OF THE INVENTION
The main object of the present invention is to provide a method and apparatus that can increase the efficiency of the QS or NFS algorithms by one to two orders of magnitude. The main practical significance of such an improvement is that it can make 512 bit numbers (which are the default setting today of most Internet browsers in e-commerce applications) relatively easy to factor. The technique of the present invention is based on a very simple optoelectronic device which can analyse long sequences of large integers, and determine which ones factor completely over a prime base consisting of the first k prime numbers for some large k.
The present inventive method and apparatus is based on a novel optoelectronic device called TWINKLE (The Weizmann INstitute Key Locating Engine). The manufacturing cost of these devices in full production is deemed to be a modest sum. It can be combined with an algorithm, such as, any sieve-based factoring algorithm, and in particular it can be used in both the QS and the NFS algorithms. It uses their basic mathematical structure and inherits their asymptotic complexity, but improves the practical efficiency of their sieving stage by a large constant factor. Since this is the most time consuming part of these algorithms, a major improvement in their total running time is obtained.
Further objects and advantages of the present invention will become readily apparent from the following detailed description of a preferred embodiment of the invention when taken with the appended drawings.
REFERENCES:
patent: 4519046 (1985-05-01), Cole
patent: 4837822 (1989-06-01), Crosley et al.
patent: 5142579 (1992-08-01), Anderson
patent: 5295188 (1994-03-01), Wilson
patent: 6091819 (2000-07-01), Venkatesan et al.
patent: 6134325 (2000-10-01), Vanstone et al.
patent: 6141420 (2000-10-01), Vanstone
patent: 6266771 (2001-07-01), Bellare et al.
patent: 6298135 (2001-10-01), Messerges
patent: 6343280 (2002-01-01), Clark
Abdulselam Abbas
Bianco Paul D.
Fleit Martin
Fleit Kain Gibbons Gutman & Bongini P.L.
Hjerpe Richard
LandOfFree
Method and apparatus for factoring large numbers with... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for factoring large numbers with..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for factoring large numbers with... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3112999