Factoring polynomials using fewer random bits

✍ Scribed by Eric Bach; Victor Shoup

• Book ID: 104344958
• Publisher: Elsevier Science
• Year: 1990
• Tongue: English
• Weight: 629 KB
• Volume: 9
• Category: Article
• ISSN: 0747-7171
• DOI: 10.1016/s0747-7171(08)80011-9

✦ Synopsis

Let F be a field of q = p" elements, where p is prime. We present two new probabilistic algorithms for factoring polynomials in FIX] that make particularly efficient use of random bits. They are easy to implement, and require no randomness beyond an initial seed whose length is proportional to the input size. The first algorithm is based on a procedure of Berlekamp; on input f in FIX] of degree d, it uses dlog 2 p random bits and produces in polynomial time a complete factorisation of f with a failure probability of no more than lip c1-'~'t/2. (Here ~ denotes a fixed parameter between 0 and 1 that can be chosen by the implementer.) The second algorithm is based on a method of Cantor and Zassenhaus; it uses d logz q random bits and fails to find a complete factorisation with probability no more than 1/qC1-,~/4. For both of these algorithms, the failure probability is exponentially small in the number of random bits used.