Volume 15 Number 3 (May. 2020)
Home > Archive > 2020 > Volume 15 Number 3 (May. 2020) >
JSW 2020 Vol.15(3): 86-97 ISSN: 1796-217X
doi: 10.17706/jsw.15.3.86-97

Algorithm Available for Factoring Big Fermat Numbers

Xingbo Wang1,2,3*
1Department of Mechatronic Engineering, Foshan University, Foshan City, PRC, 528000, China.
2State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China.
3Guangdong Engineering Center of Information Security for Intelligent Manufacturing System, China.


Abstract—The paper proves that an odd composite integer N can be factorized in at most O( 0.125u (log2N)2) searching steps if N has a divisor of the form 2au +1 or 2au-1 with a >1 being a positive integer and u>1 being an odd integer. Theorems and corollaries are proved with detail mathematical reasoning. Algorithms to factorize the kind of odd composite integers are designed and tested with certain Fermat numbers. The results in the paper might be helpful to factorize certain big Fermat numbers.

Index Terms—Algorithm, integer factorization, fermat number, cryptography.

[PDF]

Cite: Xingbo Wang, "Algorithm Available for Factoring Big Fermat Numbers," Journal of Software vol. 15, no. 3, pp. 86-97, 2020.

Copyright © 2020 by the authors. This is an open access article distributed under the Creative Commons Attribution License which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited (CC BY 4.0).

General Information

ISSN: 1796-217X (Online)
Frequency: Monthly (2006-2019); Bimonthly (Since 2020)
Editor-in-Chief: Prof. Antanas Verikas
Executive Editor: Ms. Yoyo Y. Zhou
Abstracting/ Indexing: DBLP, EBSCO, Google Scholar, ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat, etc
E-mail: jsw@iap.org
  • Dec 06, 2019 News!

    Vol 14, No 1- Vol 14, No 4 has been indexed by EI (Inspec)   [Click]

  • Jun 22, 2020 News!

    Papers published in JSW Vol 14, No 1- Vol 15 No 4 have been indexed by DBLP     [Click]

  • Sep 30, 2020 News!

    The papers published in Vol 15, No 6 have all received dois from Crossref   [Click]

  • Aug 01, 2018 News!

    [CFP] 2020 the annual meeting of JSW Editorial Board, ICCSM 2020, will be held in Rome, Italy, July 17-19, 2020   [Click]

  • Sep 30, 2020 News!

    Vol 15, No 6 has been published with online version     [Click]