Using Lucas sequences to factor large integers near group orders.

MaRDI QIDQ2735219zbMATH OpenFDO

Authors Zhenxiang Zhang

Publication date 2001

Published in The Fibonacci Quarterly (Search for Journal in Brave)

Mathematics Subject Classification ID

Factorization; primality (11A51) Fibonacci and Lucas numbers and polynomials and generalizations (11B39) Factorization (11Y05)

Review text

Using Lucas sequences, the author proves two theorems. Theorem 1. There exists an algorithm for finding prime divisors \(p<q\) of \(N\) in \(O(\log^3N+| r| \log^2N )\) bit operations, provided \(N=pq\) with \(q=k(p-1)+r\) and \(| r| <(p-3)/2\). Theorem 2. There exists an algorithm for finding prime divisors \(p<q\) of \(N\) in \(O(\log^3N+| r| \log^2N )\) bit operations, provided \(N=pq\) with \(q=k(p+1)+r\) and \(| r| <(p+1)/2\).

Recommendations

• scientific article; zbMATH DE number 3959522
• scientific article; zbMATH DE number 475434
• scientific article; zbMATH DE number 3991578
• scientific article; zbMATH DE number 177024
• A Note on Primality Testing Using Lucas Sequences

Cited in

(3)

• A one-parameter quadratic-base version of the Baillie-PSW probable prime test
• Finding strong pseudoprimes to several bases. II
• Introducing \(S\)-index into factoring RSA modulus via Lucas sequences

This page was built for publication: Using Lucas sequences to factor large integers near group orders.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2735219)