3752:
226:
704:
202:), even the fastest prime factorization algorithms on the fastest computers can take enough time to make the search impractical; that is, as the number of digits of the integer being factored increases, the number of operations required to perform the factorization on any computer increases drastically.
1956:
274:
by repeated application of this algorithm. The situation is more complicated with special-purpose factorization algorithms, whose benefits may not be realized as well or even at all with the factors produced during decomposition. For example, if
2222:
Kleinjung, Thorsten; Aoki, Kazumaro; Franke, Jens; Lenstra, Arjen K.; Thomé, Emmanuel; Bos, Joppe W.; Gaudry, Pierrick; Kruppa, Alexander; Montgomery, Peter L.; Osvik, Dag Arne; te Riele, Herman J. J.; Timofeev, Andrey; Zimmermann, Paul (2010).
548:
990:
A special-purpose factoring algorithm's running time depends on the properties of the number to be factored or on one of its unknown factors: size, special form, etc. The parameters which determine the running time vary among algorithms.
1002:
algorithms, whose running time depends on the size of smallest prime factor. Given an integer of unknown form, these methods are usually applied before general-purpose methods to remove small factors. For example, naive
1316:
3623:
2770:
Chapter 5: Exponential
Factoring Algorithms, pp. 191â226. Chapter 6: Subexponential Factoring Algorithms, pp. 227â284. Section 7.4: Elliptic curve method, pp. 301â313.
1829:
136:. For larger numbers, especially when using a computer, various more sophisticated factorization algorithms are more efficient. A prime factorization algorithm typically involves
393:. While these are easily recognized as composite and prime respectively, Fermat's method will take much longer to factor the composite number because the starting value of
2920:
93:
is a prime number because it cannot be decomposed in this way. If one of the factors is composite, it can in turn be written as a product of smaller factors, for example
699:{\displaystyle \exp \left(\left(\left({\tfrac {8}{3}}\right)^{\frac {2}{3}}+o(1)\right)\left(\log n\right)^{\frac {1}{3}}\left(\log \log n\right)^{\frac {2}{3}}\right).}
3627:
2204:
816:
796:
3135:
445:) utilizing approximately 900 core-years of computing power. The researchers estimated that a 1024-bit RSA modulus would take about 500 times as long.
441:
In 2019, Fabrice Boudot, Pierrick Gaudry, Aurore
Guillevic, Nadia Heninger, Emmanuel Thomé and Paul Zimmermann factored a 240-digit (795-bit) number (
2913:
2401:
Vandersypen, Lieven M. K.; et al. (2001). "Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance".
3168:
2074:
842:, meaning that both "yes" and "no" answers can be verified in polynomial time. An answer of "yes" can be certified by exhibiting a factorization
2073:
To obtain an algorithm for factoring any positive integer, it is necessary to add a few steps to this algorithm such as trial division, and the
4113:
2118:
452:, an 829-bit number with 250 decimal digits, in February 2020. The total computation time was roughly 2700 core-years of computing using Intel
47:
17:
1177:
456:
6130 at 2.1 GHz. Like all recent factorization records, this factorization was completed with a highly optimized implementation of the
1105:
algorithm, has a running time which depends solely on the size of the integer to be factored. This is the type of algorithm used to factor
190:
Not all numbers of a given length are equally hard to factor. The hardest instances of these problems (for currently known techniques) are
4108:
3004:
2968:
2906:
2700:
909:
guarantees that there is only one possible string of increasing primes that will be accepted, which shows that the problem is in both
4103:
3695:
3492:
3128:
1353:
The
SchnorrâSeysenâLenstra probabilistic algorithm has been rigorously proven by Lenstra and Pomerance to have expected running time
205:
Many cryptographic protocols are based on the difficulty of factoring large composite integers or a related problemâfor example, the
505:. Neither the existence nor non-existence of such algorithms has been proved, but it is generally suspected that they do not exist.
453:
2999:
1031:
969:
that can test primality very quickly in practice if one is willing to accept a vanishingly small possibility of error. The ease of
2232:
Advances in
Cryptology - CRYPTO 2010, 30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15-19, 2010. Proceedings
3360:
1143:
2841:
2812:
2579:
2562:
2507:
2378:
2320:
2275:
2183:
3302:
3121:
1057:
3231:
3408:
31:
3741:
2929:
2791:
2763:
2208:
906:
244:
152:
198:
long, randomly chosen, and about the same size (but not too close, for example, to avoid efficient factorization by
3938:
3355:
3317:
3292:
3206:
1371:
1122:
1062:
1035:
199:
3497:
3388:
3307:
3297:
3236:
3199:
2778:
1117:
1067:
3751:
3325:
3173:
3076:
3046:
1342:
438:
whose factors are of similar size. For this reason, these are the integers used in cryptographic applications.
3056:
3688:
3578:
2963:
2351:
Buhler, J. P.; Lenstra, H. W. Jr.; Pomerance, Carl (1993). "Factoring integers with the number field sieve".
1951:{\displaystyle \left(\prod _{x\in X_{}}x^{r(x)}\right).\left(\prod _{q\in P_{\Delta }}f_{q}^{t(q)}\right)=1.}
1046:
423:
2465:
3573:
3540:
3502:
3403:
3454:
3092:
2107:
1427:
is an odd positive integer greater than a certain constant. In this factoring algorithm the discriminant
164:
102:
3892:
3928:
3619:
3609:
3568:
3344:
3338:
3312:
3183:
3030:
2994:
2973:
1138:
1072:
1021:
750:
527:
457:
523:
270:
Given a general algorithm for integer factorization, any integer can be factored into its constituent
3913:
3604:
3545:
3071:
1516:
1077:
2989:
2877:
3681:
3507:
3380:
3226:
3178:
2128:
267:. If composite, however, the polynomial time tests give no insight into how to obtain the factors.
4057:
194:, the product of two prime numbers. When they are both large, for instance more than two thousand
4067:
3933:
3857:
3522:
3097:
2834:
2086:
1638:
180:
3413:
2554:
2547:
1602:
The relation that will be used is a relation between the product of powers that is equal to the
69:
of integers. Every positive integer greater than 1 is either the product of two or more integer
4118:
3918:
3877:
3633:
3583:
3563:
2798:
1168:
In number theory, there are many integer factoring algorithms that heuristically have expected
920:
The problem is suspected to be outside all three of the complexity classes P, NP-complete, and
30:"Prime decomposition" redirects here. For the prime decomposition theorem for 3-manifolds, see
2876:, Neeraj Kayal, Nitin Saxena, "PRIMES is in P." Annals of Mathematics 160(2): 781â793 (2004).
2522:
2302:
2257:
151:
is known. However, it has not been proven that such an algorithm does not exist. The presumed
3847:
3643:
3259:
3188:
2958:
2948:
2663:
1330:
1110:
66:
4021:
3923:
3638:
3530:
3512:
3487:
3449:
3193:
3066:
2729:
2648:
2603:
2517:
2422:
2330:
2285:
966:
749:-bit number inputs. In 2001, Shor's algorithm was implemented for the first time, by using
434:-bit numbers, the most difficult to factor in practice using existing algorithms are those
8:
4082:
4077:
3872:
3867:
3852:
3791:
3648:
3614:
3535:
3439:
3398:
3393:
3370:
3274:
2825:
2163:
2112:
1603:
1156:
1016:
724:
3060:
3050:
2883:
2863:
Richard P. Brent, "Recent
Progress and Prospects for Integer Factorisation Algorithms",
2426:
4006:
4001:
3962:
3882:
3862:
3479:
3426:
3423:
3264:
3213:
3163:
2623:"A probabilistic factorization algorithm with quadratic forms of negative discriminant"
2446:
2412:
2334:
1341:
proposed by
Schnorr, Seysen, and Lenstra, which they proved only assuming the unproved
962:
896:
801:
781:
264:
160:
3673:
3220:
2720:
2682:
2639:
2622:
943:
a prime number?") appears to be much easier than the problem of specifying factors of
4042:
3982:
3599:
3555:
3269:
3246:
2898:
2837:
2808:
2787:
2759:
2595:
2558:
2503:
2491:
2438:
2374:
2338:
2316:
2271:
2179:
2141:
1363:
1097:
716:
2860:â SIQS and NFS â has helped complete some of the largest public factorizations known
2049:
is found. In order to prevent useless ambiguous forms from generating, build up the
1991:
of order dividing 2 to obtain a coprime factorization of the largest odd divisor of
1362:
by replacing the GRH assumption with the use of multipliers. The algorithm uses the
4072:
4047:
3967:
3953:
3887:
3771:
3731:
3444:
3025:
2873:
2747:
2715:
2678:
2634:
2591:
2450:
2430:
2403:
2366:
2358:
2308:
2263:
2253:
2235:
2171:
2133:
1484:
761:
757:
184:
172:
144:
74:
62:
2607:
2175:
526:. As of 2022, the algorithm with best theoretical asymptotic running time is the
4052:
3977:
3971:
3908:
3806:
3796:
3726:
3434:
3333:
2725:
2644:
2599:
2513:
2326:
2281:
2239:
2234:. Lecture Notes in Computer Science. Vol. 6223. Springer. pp. 333â350.
1334:
1169:
1128:
1025:
974:
925:
910:
835:
473:
449:
260:
210:
4062:
4016:
3842:
3826:
3816:
3786:
3464:
3365:
3350:
3254:
3155:
3102:
3020:
2830:
2751:
2538:
2487:
2479:
2050:
1367:
1322:
1133:
1011:
1004:
970:
921:
490:
300:
256:
176:
137:
113:
44:
Can integer factorization be solved in polynomial time on a classical computer?
3113:
2267:
949:. The composite/prime problem can be solved in polynomial time (in the number
4097:
4011:
3811:
3801:
3781:
3459:
3144:
2483:
2312:
2298:
2123:
1451:
252:
2045:
then stop, otherwise find another ambiguous form until the factorization of
225:
36:
4026:
3943:
3821:
3766:
3736:
3469:
2773:
2442:
271:
248:
156:
78:
2868:
2857:
2664:"Fast and rigorous factorization under the generalized Riemann hypothesis"
2357:. Lecture Notes in Mathematics. Vol. 1554. Springer. pp. 50â94.
1615:. These relations will be used to construct a so-called ambiguous form of
209:. An algorithm that efficiently factors an arbitrary integer would render
2953:
2495:
2417:
977:
algorithm, as it is necessary to find large prime numbers to start with.
206:
168:
129:
54:
2802:
2466:"Computational Complexity Blog: Complexity Class of the Week: Factoring"
883:. An answer of "no" can be certified by exhibiting the factorization of
2892:
2542:
2502:, Princeton, New Jersey: Princeton University Press, pp. 575â604,
2362:
2224:
1633:
of order dividing 2. By calculating the corresponding factorization of
1326:
1106:
720:
435:
214:
2259:
The Proof is in the
Pudding: The Changing Nature of Mathematical Proof
2205:"[Cado-nfs-discuss] 795-bit factoring and discrete logarithms"
1311:{\displaystyle L_{n}\left=e^{(1+o(1)){\sqrt {(\log n)(\log \log n)}}}}
709:
For current computers, GNFS is the best published algorithm for large
3776:
3147:
2370:
2352:
1467:
can be restricted to a small set to guarantee the smoothness result.
994:
An important subclass of special-purpose factoring algorithms is the
469:
191:
148:
2434:
101:; the result is always unique up to the order of the factors by the
2746:
1641:, this ambiguous form provides the complete prime factorization of
723:
discovered an algorithm in 1994 that solves it in polynomial time.
3721:
2089:
as it makes random choices. Its expected running time is at most
442:
112:
using mental or pen-and-paper arithmetic, the simplest method is
70:
2580:"Refined analysis and improvements on some factoring algorithms"
1446:
is some positive multiplier. The algorithm expects that for one
309:
divisions to find the next factor. As a contrasting example, if
97:. Continuing this process until every factor is prime is called
3992:
2537:
1109:. Most general-purpose factoring algorithms are based on the
839:
95:
60 = 3 · 20 = 3 · (5 · 4)
760:
such as P, NP, and co-NP, the problem has to be stated as a
2221:
2144:â a way of writing a number as a sum of positive integers.
1561:
a sequence of relations between the set of generators and
2794:. Section 4.5.4: Factoring into Primes, pp. 379â417.
914:
195:
303:
will quickly produce the factors 3 and 19 but will take
155:
of this problem is important for the algorithms used in
3703:
3664:
indicate that algorithm is for numbers of special forms
2115:
for generating random numbers with their factorizations
1088:
A general-purpose factoring algorithm, also known as a
116:: checking if the number is divisible by prime numbers
2928:
2797:
2350:
2307:, Cambridge: Cambridge University Press, p. 230,
2166:, in van Tilborg, Henk C. A.; Jajodia, Sushil (eds.),
1197:
574:
143:
When the numbers are sufficiently large, no efficient
2533:
2531:
1832:
1180:
804:
784:
551:
2694:
2692:
1676:
is the negative discriminant of some quadratic form.
508:
There are published algorithms that are faster than
175:
have been brought to bear on the problem, including
38:
1414:
753:techniques on molecules that provide seven qubits.
472:has been published that can factor all integers in
2546:
2528:
2478:
2041:If the ambiguous form provides a factorization of
1950:
1310:
810:
790:
698:
2807:. Providence, RI: American Mathematical Society.
2689:
4095:
2698:
1463:. Lenstra and Pomerance show that the choice of
331:, Fermat's factorization method will begin with
3143:
2893:Dario Alpern's Integer factorization calculator
2701:"A Rigorous Time Bound for Factoring Integers"
2119:Canonical representation of a positive integer
530:(GNFS), first published in 1993, running on a
3689:
3129:
2914:
2699:Lenstra, H. W.; Pomerance, Carl (July 1992).
2486:(2008), "IV.20 Computational Complexity", in
2463:
2170:, Boston, MA: Springer US, pp. 611â618,
77:, or it is not, in which case it is called a
73:greater than 1, in which case it is called a
2708:Journal of the American Mathematical Society
2655:
2571:
2553:. Key College Publishing/Springer. pp.
1796:Collect a sequence of relations between set
1411:in which those integers are relative prime.
1329:. Some examples of those algorithms are the
448:The largest such semiprime yet factored was
259:whether the integer is prime can be done in
48:(more unsolved problems in computer science)
2614:
2400:
1150:
937:a composite number?" (or equivalently: "Is
895:; one can verify their primality using the
417:
3696:
3682:
3136:
3122:
2921:
2907:
2756:Prime Numbers: A Computational Perspective
2297:
2719:
2638:
2416:
2354:The development of the number field sieve
2168:Encyclopedia of Cryptography and Security
1163:
2895:â A web app for factoring large integers
2225:"Factorization of a 768-Bit RSA Modulus"
2080:
1348:
1032:Algebraic-group factorization algorithms
224:
27:Decomposition of a number into a product
2786:, Third Edition. Addison-Wesley, 1997.
2661:
2577:
2549:A Course in Computational Number Theory
2161:
1645:. This algorithm has these main steps:
980:
14:
4096:
2822:
2620:
2500:The Princeton Companion to Mathematics
2252:
931:In contrast, the decision problem "Is
924:. It is therefore a candidate for the
889:into distinct primes, all larger than
247:, every positive integer has a unique
220:
4114:Unsolved problems in computer science
3677:
3117:
2902:
2215:
1058:Lenstra elliptic curve factorization
138:testing whether each factor is prime
39:Unsolved problem in computer science
3704:Divisibility-based sets of integers
2262:, New York: Springer, p. 203,
1144:Shanks's square forms factorization
899:, and then multiply them to obtain
24:
4109:Computational hardness assumptions
2930:Computational hardness assumptions
1906:
1395:is the set of triples of integers
1083:
1024:, which has two common flavors to
985:
715:(more than about 400 bits). For a
463:
32:Prime decomposition of 3-manifolds
25:
4130:
3742:Fundamental theorem of arithmetic
3345:Special number field sieve (SNFS)
3339:General number field sieve (GNFS)
2851:
2721:10.1090/S0894-0347-1992-1137100-0
2640:10.1090/S0025-5718-1987-0878705-X
965:. In addition, there are several
907:fundamental theorem of arithmetic
245:fundamental theorem of arithmetic
4104:Integer factorization algorithms
3750:
2969:Decisional composite residuosity
1415:SchnorrâSeysenâLenstra algorithm
1337:. Another such algorithm is the
1123:Continued fraction factorization
1028:: one by Floyd and one by Brent.
913:and co-UP. It is known to be in
2779:The Art of Computer Programming
2472:
2457:
2394:
2344:
2291:
2246:
2197:
2155:
1932:
1926:
1872:
1866:
1652:be the number to be factored.
1343:generalized Riemann hypothesis
1301:
1283:
1280:
1268:
1263:
1260:
1254:
1242:
1226:
1220:
612:
606:
85:is a composite number because
13:
1:
2823:Warren, Henry S. Jr. (2013).
2740:
2683:10.1016/S1385-7258(88)80022-2
2176:10.1007/978-1-4419-5906-5_455
2085:The algorithm as stated is a
1423:that will be factored, where
1063:Fermat's factorization method
917:because of Shor's algorithm.
476:, that is, that can factor a
460:run on hundreds of machines.
424:Integer factorization records
329:13729 Ă 1372933 = 18848997157
315:is the product of the primes
200:Fermat's factorization method
140:each time a factor is found.
108:To factorize a small integer
18:Integer factorization problem
3303:Lenstra elliptic curve (ECM)
3005:Computational DiffieâHellman
2865:Computing and Combinatorics"
2596:10.1016/0196-6774(82)90012-8
2464:Lance Fortnow (2002-09-13).
2240:10.1007/978-3-642-14623-7_18
1962:Construct an ambiguous form
1339:class group relations method
1118:Dixon's factorization method
1068:Euler's factorization method
7:
3093:Exponential time hypothesis
2108:Aurifeuillean factorization
2101:
1661:be a negative integer with
1515:. By constructing a set of
1431:is chosen as a multiple of
1007:is a Category 1 algorithm.
824:have a factor smaller than
251:. (By convention, 1 is the
103:prime factorization theorem
10:
4135:
3610:Exponentiation by squaring
3293:Continued fraction (CFRAC)
2627:Mathematics of Computation
2578:Schnorr, Claus P. (1982).
2162:Lenstra, Arjen K. (2011),
1739:be a random prime form of
1572:are produced. The size of
1139:General number field sieve
1073:Special number field sieve
834:It is known to be in both
778:For every natural numbers
528:general number field sieve
458:general number field sieve
421:
61:is the decomposition of a
29:
4035:
3991:
3952:
3939:Superior highly composite
3901:
3835:
3759:
3748:
3709:
3657:
3592:
3554:
3521:
3478:
3422:
3379:
3283:
3245:
3154:
3103:Planted clique conjecture
3085:
3072:Ring learning with errors
3039:
3013:
3000:Decisional DiffieâHellman
2982:
2936:
2671:Indagationes Mathematicae
2662:Lenstra, Arjen K (1988).
2268:10.1007/978-0-387-48744-1
1624:, which is an element of
1078:Difference of two squares
973:is a crucial part of the
344:which immediately yields
161:RSA public-key encryption
3836:Constrained divisor sums
2784:Seminumerical Algorithms
2313:10.1017/CBO9780511804090
2304:Computational complexity
2148:
2129:Multiplicative partition
1151:Other notable algorithms
967:probabilistic algorithms
418:Current state of the art
3523:Greatest common divisor
3098:Unique games conjecture
3047:Shortest vector problem
3021:External DiffieâHellman
2886:MathWorld Headline News
2878:August 2005 version PDF
2867:, 2000, pp. 3â22.
2835:Pearson Education, Inc.
2621:Seysen, Martin (1987).
2230:. In Rabin, Tal (ed.).
2087:probabilistic algorithm
1159:, for quantum computers
1022:Pollard's rho algorithm
773:(Integer factorization)
756:In order to talk about
410:is a factor of 10 from
299:are very large primes,
229:Prime decomposition of
217:cryptography insecure.
181:algebraic number theory
128:, and so on, up to the
3634:Modular exponentiation
3077:Short integer solution
3057:Closest vector problem
2799:Samuel S. Wagstaff Jr.
2610:on September 24, 2017.
2301:; Barak, Boaz (2009),
1952:
1780:Find a generating set
1479:the set of all primes
1312:
1164:Heuristic running time
812:
792:
700:
371:and hence the factors
263:, for example, by the
240:
147:integer factorization
87:15 = 3 · 5
3717:Integer factorization
3361:Shanks's square forms
3285:Integer factorization
3260:Sieve of Eratosthenes
2964:Quadratic residuosity
2944:Integer factorization
2584:Journal of Algorithms
2081:Expected running time
1953:
1349:Rigorous running time
1331:elliptic curve method
1313:
1111:congruence of squares
1026:identify group cycles
813:
793:
701:
228:
165:RSA digital signature
59:integer factorization
3639:Montgomery reduction
3513:Function field sieve
3488:Baby-step giant-step
3334:Quadratic sieve (QS)
3067:Learning with errors
2804:The Joy of Factoring
2521:. See in particular
1830:
1672:is a multiplier and
1178:
981:Factoring algorithms
802:
782:
549:
3929:Colossally abundant
3760:Factorization forms
3649:Trachtenberg system
3615:Integer square root
3556:Modular square root
3275:Wheel factorization
3227:Quadratic Frobenius
3207:LucasâLehmerâRiesel
2884:âRSA-640 Factoredâ
2882:Eric W. Weisstein,
2427:2001Natur.414..883V
2164:"Integer Factoring"
1978:that is an element
1936:
1450:there exist enough
1366:of positive binary
1017:Wheel factorization
776: —
249:prime factorization
221:Prime decomposition
99:prime factorization
3914:Primitive abundant
3902:With many divisors
3541:Extended Euclidean
3480:Discrete logarithm
3409:SchönhageâStrassen
3265:Sieve of Pritchard
2990:Discrete logarithm
2974:Higher residuosity
2888:, November 8, 2005
2492:Barrow-Green, June
2363:10.1007/BFb0091539
1948:
1913:
1912:
1857:
1590:for some constant
1576:can be bounded by
1308:
1206:
1034:, among which are
963:AKS primality test
928:complexity class.
897:AKS primality test
808:
788:
770:
758:complexity classes
696:
583:
499:for some constant
265:AKS primality test
241:
4091:
4090:
3671:
3670:
3270:Sieve of Sundaram
3111:
3110:
3086:Non-cryptographic
2843:978-0-321-84268-8
2814:978-1-4704-1048-3
2564:978-1-930190-10-8
2509:978-0-691-11880-2
2411:(6866): 883â887.
2380:978-3-540-57013-4
2322:978-0-521-42426-4
2277:978-0-387-48908-7
2254:Krantz, Steven G.
2185:978-1-4419-5905-8
2142:Integer partition
1890:
1838:
1419:Given an integer
1304:
1205:
971:primality testing
811:{\displaystyle k}
791:{\displaystyle n}
768:
685:
648:
597:
582:
516:for all positive
510:O((1 +
185:quantum computing
16:(Redirected from
4126:
4068:Harmonic divisor
3954:Aliquot sequence
3934:Highly composite
3858:Multiply perfect
3754:
3732:Divisor function
3698:
3691:
3684:
3675:
3674:
3620:Integer relation
3593:Other algorithms
3498:Pollard kangaroo
3389:Ancient Egyptian
3247:Prime-generating
3232:SolovayâStrassen
3145:Number-theoretic
3138:
3131:
3124:
3115:
3114:
3026:Sub-group hiding
2937:Number theoretic
2923:
2916:
2909:
2900:
2899:
2874:Manindra Agrawal
2847:
2826:Hacker's Delight
2818:
2769:
2748:Richard Crandall
2734:
2733:
2723:
2705:
2696:
2687:
2686:
2668:
2659:
2653:
2652:
2642:
2633:(178): 757â780.
2618:
2612:
2611:
2606:. Archived from
2575:
2569:
2568:
2552:
2535:
2526:
2520:
2476:
2470:
2469:
2461:
2455:
2454:
2420:
2418:quant-ph/0112176
2398:
2392:
2391:
2389:
2387:
2348:
2342:
2341:
2295:
2289:
2288:
2250:
2244:
2243:
2229:
2219:
2213:
2212:
2207:. Archived from
2201:
2195:
2194:
2193:
2192:
2159:
2136:
2113:Bach's algorithm
2097:
2067:
2060:
2048:
2044:
2037:
2017:
2001:
1994:
1990:
1977:
1957:
1955:
1954:
1949:
1941:
1937:
1935:
1921:
1911:
1910:
1909:
1881:
1877:
1876:
1875:
1856:
1855:
1854:
1823:
1799:
1792:
1783:
1776:
1774:
1771:
1770:
1768:
1767:
1762:
1759:
1752:
1747:
1738:
1724:
1714:
1682:
1675:
1671:
1667:
1660:
1651:
1644:
1637:and by taking a
1636:
1632:
1623:
1614:
1598:
1589:
1587:
1575:
1571:
1560:
1551:
1547:
1538:
1528:and prime forms
1527:
1514:
1512:
1509:
1508:
1506:
1505:
1500:
1497:
1490:
1485:Kronecker symbol
1482:
1478:
1466:
1462:
1449:
1445:
1441:
1434:
1430:
1426:
1422:
1410:
1394:
1385:
1376:
1361:
1317:
1315:
1314:
1309:
1307:
1306:
1305:
1267:
1233:
1229:
1207:
1198:
1190:
1189:
1157:Shor's algorithm
1053:
1042:
960:
954:
948:
942:
936:
904:
894:
888:
882:
872:
870:
868:
867:
862:
859:
829:
823:
817:
815:
814:
809:
797:
795:
794:
789:
777:
774:
769:Decision problem
762:decision problem
748:
742:
734:
725:Shor's algorithm
717:quantum computer
714:
705:
703:
702:
697:
692:
688:
687:
686:
678:
676:
672:
650:
649:
641:
639:
635:
619:
615:
599:
598:
590:
588:
584:
575:
541:
535:
521:
515:
504:
498:
487:
481:
433:
413:
409:
403:
401:
400:
392:
381:
370:
368:
367:
361:
360:
343:
341:
340:
330:
326:
322:
318:
314:
308:
298:
288:
239:
235:
173:computer science
167:. Many areas of
135:
127:
123:
119:
111:
96:
92:
88:
84:
75:composite number
63:positive integer
40:
21:
4134:
4133:
4129:
4128:
4127:
4125:
4124:
4123:
4094:
4093:
4092:
4087:
4031:
3987:
3948:
3919:Highly abundant
3897:
3878:Unitary perfect
3831:
3755:
3746:
3727:Unitary divisor
3705:
3702:
3672:
3667:
3653:
3588:
3550:
3517:
3474:
3418:
3375:
3279:
3241:
3214:Proth's theorem
3156:Primality tests
3150:
3142:
3112:
3107:
3081:
3035:
3031:Decision linear
3009:
2983:Group theoretic
2978:
2932:
2927:
2854:
2844:
2815:
2766:
2743:
2738:
2737:
2703:
2697:
2690:
2666:
2660:
2656:
2619:
2615:
2576:
2572:
2565:
2536:
2529:
2510:
2488:Gowers, Timothy
2480:Goldreich, Oded
2477:
2473:
2462:
2458:
2435:10.1038/414883a
2399:
2395:
2385:
2383:
2381:
2349:
2345:
2323:
2296:
2292:
2278:
2251:
2247:
2227:
2220:
2216:
2203:
2202:
2198:
2190:
2188:
2186:
2160:
2156:
2151:
2137:-adic valuation
2134:
2104:
2095:
2090:
2083:
2075:Jacobi sum test
2071:
2062:
2058:
2054:
2046:
2042:
2019:
2003:
1996:
1992:
1989:
1979:
1963:
1922:
1917:
1905:
1901:
1894:
1889:
1885:
1862:
1858:
1853:
1849:
1842:
1837:
1833:
1831:
1828:
1827:
1821:
1810:
1801:
1797:
1791:
1785:
1781:
1772:
1763:
1760:
1757:
1756:
1754:
1753:
1750:
1749:
1746:
1740:
1737:
1729:
1716:
1713:
1704:
1697:
1690:
1684:
1680:
1673:
1669:
1662:
1658:
1649:
1642:
1634:
1631:
1625:
1622:
1616:
1613:
1607:
1604:neutral element
1597:
1591:
1585:
1583:
1577:
1573:
1570:
1562:
1559:
1553:
1549:
1546:
1540:
1537:
1529:
1526:
1520:
1510:
1501:
1498:
1495:
1494:
1492:
1491:
1488:
1487:
1480:
1477:
1471:
1464:
1461:
1455:
1447:
1443:
1436:
1432:
1428:
1424:
1420:
1417:
1396:
1393:
1387:
1384:
1378:
1374:
1368:quadratic forms
1359:
1354:
1351:
1335:quadratic sieve
1266:
1241:
1237:
1196:
1195:
1191:
1185:
1181:
1179:
1176:
1175:
1166:
1153:
1129:Quadratic sieve
1094:Second Category
1086:
1084:General-purpose
1048:
1037:
988:
986:Special-purpose
983:
956:
950:
944:
938:
932:
926:NP-intermediate
900:
890:
884:
874:
863:
860:
855:
854:
852:
843:
832:
825:
819:
803:
800:
799:
783:
780:
779:
775:
772:
744:
736:
728:
710:
677:
656:
652:
651:
640:
625:
621:
620:
589:
573:
569:
568:
567:
563:
562:
558:
550:
547:
546:
537:
531:
524:sub-exponential
517:
509:
500:
489:
483:
477:
474:polynomial time
466:
464:Time complexity
429:
426:
420:
411:
405:
398:
396:
394:
383:
372:
365:
363:
352:
350:
345:
342:â = 18848997159
336:
334:
332:
328:
324:
320:
316:
310:
304:
290:
276:
261:polynomial time
237:
230:
223:
177:elliptic curves
133:
125:
121:
117:
109:
94:
90:
86:
82:
81:. For example,
51:
50:
45:
42:
35:
28:
23:
22:
15:
12:
11:
5:
4132:
4122:
4121:
4116:
4111:
4106:
4089:
4088:
4086:
4085:
4080:
4075:
4070:
4065:
4060:
4055:
4050:
4045:
4039:
4037:
4033:
4032:
4030:
4029:
4024:
4019:
4014:
4009:
4004:
3998:
3996:
3989:
3988:
3986:
3985:
3980:
3975:
3965:
3959:
3957:
3950:
3949:
3947:
3946:
3941:
3936:
3931:
3926:
3921:
3916:
3911:
3905:
3903:
3899:
3898:
3896:
3895:
3890:
3885:
3880:
3875:
3870:
3865:
3860:
3855:
3850:
3848:Almost perfect
3845:
3839:
3837:
3833:
3832:
3830:
3829:
3824:
3819:
3814:
3809:
3804:
3799:
3794:
3789:
3784:
3779:
3774:
3769:
3763:
3761:
3757:
3756:
3749:
3747:
3745:
3744:
3739:
3734:
3729:
3724:
3719:
3713:
3711:
3707:
3706:
3701:
3700:
3693:
3686:
3678:
3669:
3668:
3666:
3665:
3658:
3655:
3654:
3652:
3651:
3646:
3641:
3636:
3631:
3617:
3612:
3607:
3602:
3596:
3594:
3590:
3589:
3587:
3586:
3581:
3576:
3574:TonelliâShanks
3571:
3566:
3560:
3558:
3552:
3551:
3549:
3548:
3543:
3538:
3533:
3527:
3525:
3519:
3518:
3516:
3515:
3510:
3508:Index calculus
3505:
3503:PohligâHellman
3500:
3495:
3490:
3484:
3482:
3476:
3475:
3473:
3472:
3467:
3462:
3457:
3455:Newton-Raphson
3452:
3447:
3442:
3437:
3431:
3429:
3420:
3419:
3417:
3416:
3411:
3406:
3401:
3396:
3391:
3385:
3383:
3381:Multiplication
3377:
3376:
3374:
3373:
3368:
3366:Trial division
3363:
3358:
3353:
3351:Rational sieve
3348:
3341:
3336:
3331:
3323:
3315:
3310:
3305:
3300:
3295:
3289:
3287:
3281:
3280:
3278:
3277:
3272:
3267:
3262:
3257:
3255:Sieve of Atkin
3251:
3249:
3243:
3242:
3240:
3239:
3234:
3229:
3224:
3217:
3210:
3203:
3196:
3191:
3186:
3181:
3179:Elliptic curve
3176:
3171:
3166:
3160:
3158:
3152:
3151:
3141:
3140:
3133:
3126:
3118:
3109:
3108:
3106:
3105:
3100:
3095:
3089:
3087:
3083:
3082:
3080:
3079:
3074:
3069:
3064:
3054:
3043:
3041:
3037:
3036:
3034:
3033:
3028:
3023:
3017:
3015:
3011:
3010:
3008:
3007:
3002:
2997:
2995:Diffie-Hellman
2992:
2986:
2984:
2980:
2979:
2977:
2976:
2971:
2966:
2961:
2956:
2951:
2946:
2940:
2938:
2934:
2933:
2926:
2925:
2918:
2911:
2903:
2897:
2896:
2890:
2880:
2871:
2861:
2853:
2852:External links
2850:
2849:
2848:
2842:
2831:Addison Wesley
2829:(2 ed.).
2820:
2813:
2795:
2771:
2764:
2752:Carl Pomerance
2742:
2739:
2736:
2735:
2714:(3): 483â516.
2688:
2677:(4): 443â454.
2654:
2613:
2590:(2): 101â127.
2570:
2563:
2539:David Bressoud
2527:
2508:
2484:Wigderson, Avi
2471:
2456:
2393:
2379:
2343:
2321:
2299:Arora, Sanjeev
2290:
2276:
2245:
2214:
2211:on 2019-12-02.
2196:
2184:
2153:
2152:
2150:
2147:
2146:
2145:
2139:
2131:
2126:
2121:
2116:
2110:
2103:
2100:
2093:
2082:
2079:
2070:
2069:
2056:
2039:
1987:
1960:
1959:
1958:
1947:
1944:
1940:
1934:
1931:
1928:
1925:
1920:
1916:
1908:
1904:
1900:
1897:
1893:
1888:
1884:
1880:
1874:
1871:
1868:
1865:
1861:
1852:
1848:
1845:
1841:
1836:
1819:
1806:
1794:
1789:
1778:
1744:
1733:
1726:
1709:
1702:
1695:
1688:
1677:
1654:
1629:
1620:
1611:
1595:
1581:
1566:
1557:
1544:
1533:
1524:
1475:
1459:
1416:
1413:
1391:
1382:
1357:
1350:
1347:
1319:
1318:
1303:
1300:
1297:
1294:
1291:
1288:
1285:
1282:
1279:
1276:
1273:
1270:
1265:
1262:
1259:
1256:
1253:
1250:
1247:
1244:
1240:
1236:
1232:
1228:
1225:
1222:
1219:
1216:
1213:
1210:
1204:
1201:
1194:
1188:
1184:
1165:
1162:
1161:
1160:
1152:
1149:
1148:
1147:
1141:
1136:
1134:Rational sieve
1131:
1126:
1120:
1085:
1082:
1081:
1080:
1075:
1070:
1065:
1060:
1029:
1019:
1014:
1012:Trial division
1005:trial division
1000:First Category
987:
984:
982:
979:
922:co-NP-complete
807:
787:
766:
707:
706:
695:
691:
684:
681:
675:
671:
668:
665:
662:
659:
655:
647:
644:
638:
634:
631:
628:
624:
618:
614:
611:
608:
605:
602:
596:
593:
587:
581:
578:
572:
566:
561:
557:
554:
465:
462:
419:
416:
301:trial division
222:
219:
114:trial division
46:
43:
37:
26:
9:
6:
4:
3:
2:
4131:
4120:
4119:Factorization
4117:
4115:
4112:
4110:
4107:
4105:
4102:
4101:
4099:
4084:
4081:
4079:
4076:
4074:
4071:
4069:
4066:
4064:
4061:
4059:
4056:
4054:
4051:
4049:
4046:
4044:
4041:
4040:
4038:
4034:
4028:
4025:
4023:
4022:Polydivisible
4020:
4018:
4015:
4013:
4010:
4008:
4005:
4003:
4000:
3999:
3997:
3994:
3990:
3984:
3981:
3979:
3976:
3973:
3969:
3966:
3964:
3961:
3960:
3958:
3955:
3951:
3945:
3942:
3940:
3937:
3935:
3932:
3930:
3927:
3925:
3924:Superabundant
3922:
3920:
3917:
3915:
3912:
3910:
3907:
3906:
3904:
3900:
3894:
3893:ErdĆsâNicolas
3891:
3889:
3886:
3884:
3881:
3879:
3876:
3874:
3871:
3869:
3866:
3864:
3861:
3859:
3856:
3854:
3851:
3849:
3846:
3844:
3841:
3840:
3838:
3834:
3828:
3825:
3823:
3820:
3818:
3815:
3813:
3810:
3808:
3805:
3803:
3802:Perfect power
3800:
3798:
3795:
3793:
3790:
3788:
3785:
3783:
3780:
3778:
3775:
3773:
3770:
3768:
3765:
3764:
3762:
3758:
3753:
3743:
3740:
3738:
3735:
3733:
3730:
3728:
3725:
3723:
3720:
3718:
3715:
3714:
3712:
3708:
3699:
3694:
3692:
3687:
3685:
3680:
3679:
3676:
3663:
3660:
3659:
3656:
3650:
3647:
3645:
3642:
3640:
3637:
3635:
3632:
3629:
3625:
3621:
3618:
3616:
3613:
3611:
3608:
3606:
3603:
3601:
3598:
3597:
3595:
3591:
3585:
3582:
3580:
3577:
3575:
3572:
3570:
3569:Pocklington's
3567:
3565:
3562:
3561:
3559:
3557:
3553:
3547:
3544:
3542:
3539:
3537:
3534:
3532:
3529:
3528:
3526:
3524:
3520:
3514:
3511:
3509:
3506:
3504:
3501:
3499:
3496:
3494:
3491:
3489:
3486:
3485:
3483:
3481:
3477:
3471:
3468:
3466:
3463:
3461:
3458:
3456:
3453:
3451:
3448:
3446:
3443:
3441:
3438:
3436:
3433:
3432:
3430:
3428:
3425:
3421:
3415:
3412:
3410:
3407:
3405:
3402:
3400:
3397:
3395:
3392:
3390:
3387:
3386:
3384:
3382:
3378:
3372:
3369:
3367:
3364:
3362:
3359:
3357:
3354:
3352:
3349:
3347:
3346:
3342:
3340:
3337:
3335:
3332:
3330:
3328:
3324:
3322:
3320:
3316:
3314:
3313:Pollard's rho
3311:
3309:
3306:
3304:
3301:
3299:
3296:
3294:
3291:
3290:
3288:
3286:
3282:
3276:
3273:
3271:
3268:
3266:
3263:
3261:
3258:
3256:
3253:
3252:
3250:
3248:
3244:
3238:
3235:
3233:
3230:
3228:
3225:
3223:
3222:
3218:
3216:
3215:
3211:
3209:
3208:
3204:
3202:
3201:
3197:
3195:
3192:
3190:
3187:
3185:
3182:
3180:
3177:
3175:
3172:
3170:
3167:
3165:
3162:
3161:
3159:
3157:
3153:
3149:
3146:
3139:
3134:
3132:
3127:
3125:
3120:
3119:
3116:
3104:
3101:
3099:
3096:
3094:
3091:
3090:
3088:
3084:
3078:
3075:
3073:
3070:
3068:
3065:
3062:
3058:
3055:
3052:
3048:
3045:
3044:
3042:
3038:
3032:
3029:
3027:
3024:
3022:
3019:
3018:
3016:
3012:
3006:
3003:
3001:
2998:
2996:
2993:
2991:
2988:
2987:
2985:
2981:
2975:
2972:
2970:
2967:
2965:
2962:
2960:
2957:
2955:
2952:
2950:
2947:
2945:
2942:
2941:
2939:
2935:
2931:
2924:
2919:
2917:
2912:
2910:
2905:
2904:
2901:
2894:
2891:
2889:
2887:
2881:
2879:
2875:
2872:
2870:
2866:
2862:
2859:
2856:
2855:
2845:
2839:
2836:
2832:
2828:
2827:
2821:
2816:
2810:
2806:
2805:
2800:
2796:
2793:
2792:0-201-89684-2
2789:
2785:
2781:
2780:
2775:
2772:
2767:
2765:0-387-94777-9
2761:
2757:
2753:
2749:
2745:
2744:
2731:
2727:
2722:
2717:
2713:
2709:
2702:
2695:
2693:
2684:
2680:
2676:
2672:
2665:
2658:
2650:
2646:
2641:
2636:
2632:
2628:
2624:
2617:
2609:
2605:
2601:
2597:
2593:
2589:
2585:
2581:
2574:
2566:
2560:
2556:
2551:
2550:
2544:
2540:
2534:
2532:
2524:
2519:
2515:
2511:
2505:
2501:
2497:
2493:
2489:
2485:
2481:
2475:
2467:
2460:
2452:
2448:
2444:
2440:
2436:
2432:
2428:
2424:
2419:
2414:
2410:
2406:
2405:
2397:
2382:
2376:
2372:
2368:
2364:
2360:
2356:
2355:
2347:
2340:
2336:
2332:
2328:
2324:
2318:
2314:
2310:
2306:
2305:
2300:
2294:
2287:
2283:
2279:
2273:
2269:
2265:
2261:
2260:
2255:
2249:
2241:
2237:
2233:
2226:
2218:
2210:
2206:
2200:
2187:
2181:
2177:
2173:
2169:
2165:
2158:
2154:
2143:
2140:
2138:
2132:
2130:
2127:
2125:
2124:Factorization
2122:
2120:
2117:
2114:
2111:
2109:
2106:
2105:
2099:
2096:
2088:
2078:
2076:
2065:
2052:
2040:
2035:
2031:
2027:
2023:
2015:
2011:
2007:
2000:
1986:
1982:
1975:
1971:
1967:
1961:
1945:
1942:
1938:
1929:
1923:
1918:
1914:
1902:
1898:
1895:
1891:
1886:
1882:
1878:
1869:
1863:
1859:
1850:
1846:
1843:
1839:
1834:
1826:
1825:
1818:
1814:
1809:
1805:
1795:
1788:
1779:
1766:
1743:
1736:
1732:
1727:
1723:
1719:
1712:
1708:
1701:
1694:
1687:
1683:first primes
1678:
1666:
1656:
1655:
1653:
1646:
1640:
1628:
1619:
1610:
1605:
1600:
1594:
1580:
1569:
1565:
1556:
1543:
1536:
1532:
1523:
1518:
1504:
1486:
1474:
1468:
1458:
1453:
1440:
1412:
1408:
1404:
1400:
1390:
1381:
1373:
1369:
1365:
1360:
1346:
1344:
1340:
1336:
1332:
1328:
1324:
1298:
1295:
1292:
1289:
1286:
1277:
1274:
1271:
1257:
1251:
1248:
1245:
1238:
1234:
1230:
1223:
1217:
1214:
1211:
1208:
1202:
1199:
1192:
1186:
1182:
1174:
1173:
1172:
1171:
1158:
1155:
1154:
1145:
1142:
1140:
1137:
1135:
1132:
1130:
1127:
1124:
1121:
1119:
1116:
1115:
1114:
1112:
1108:
1104:
1101:
1100:
1095:
1091:
1079:
1076:
1074:
1071:
1069:
1066:
1064:
1061:
1059:
1055:
1051:
1044:
1040:
1033:
1030:
1027:
1023:
1020:
1018:
1015:
1013:
1010:
1009:
1008:
1006:
1001:
997:
992:
978:
976:
972:
968:
964:
959:
955:of digits of
953:
947:
941:
935:
929:
927:
923:
918:
916:
912:
908:
903:
898:
893:
887:
881:
877:
866:
858:
850:
846:
841:
837:
831:
828:
822:
805:
785:
765:
763:
759:
754:
752:
747:
740:
732:
726:
722:
718:
713:
693:
689:
682:
679:
673:
669:
666:
663:
660:
657:
653:
645:
642:
636:
632:
629:
626:
622:
616:
609:
603:
600:
594:
591:
585:
579:
576:
570:
564:
559:
555:
552:
545:
544:
543:
540:
534:
529:
525:
520:
513:
506:
503:
496:
492:
486:
480:
475:
471:
461:
459:
455:
451:
446:
444:
439:
437:
432:
425:
415:
408:
391:= 18848997161
390:
386:
380:= 18848997157
379:
375:
359:
355:
348:
339:
313:
307:
302:
297:
293:
287:
283:
279:
273:
272:prime factors
268:
266:
262:
258:
254:
253:empty product
250:
246:
233:
227:
218:
216:
212:
208:
203:
201:
197:
193:
188:
186:
182:
178:
174:
170:
166:
162:
158:
154:
150:
146:
141:
139:
131:
115:
106:
104:
100:
80:
76:
72:
68:
64:
60:
56:
49:
33:
19:
4083:Superperfect
4078:Refactorable
3873:Superperfect
3868:Hyperperfect
3853:Quasiperfect
3737:Prime factor
3716:
3661:
3343:
3326:
3318:
3284:
3237:MillerâRabin
3219:
3212:
3205:
3200:LucasâLehmer
3198:
2943:
2885:
2864:
2824:
2803:
2783:
2782:, Volume 2:
2777:
2774:Donald Knuth
2758:. Springer.
2755:
2711:
2707:
2674:
2670:
2657:
2630:
2626:
2616:
2608:the original
2587:
2583:
2573:
2548:
2499:
2496:Leader, Imre
2474:
2459:
2408:
2402:
2396:
2384:. Retrieved
2353:
2346:
2303:
2293:
2258:
2248:
2231:
2217:
2209:the original
2199:
2189:, retrieved
2167:
2157:
2091:
2084:
2072:
2063:
2033:
2029:
2025:
2021:
2013:
2009:
2005:
1998:
1984:
1980:
1973:
1969:
1965:
1824:satisfying:
1816:
1812:
1807:
1803:
1786:
1764:
1741:
1734:
1730:
1721:
1717:
1710:
1706:
1699:
1692:
1685:
1664:
1647:
1626:
1617:
1608:
1601:
1592:
1578:
1567:
1563:
1554:
1541:
1534:
1530:
1521:
1502:
1472:
1469:
1456:
1438:
1418:
1406:
1402:
1398:
1388:
1379:
1372:discriminant
1355:
1352:
1338:
1320:
1170:running time
1167:
1102:
1098:
1093:
1089:
1087:
1049:
1038:
999:
995:
993:
989:
957:
951:
945:
939:
933:
930:
919:
901:
891:
885:
879:
875:
864:
856:
848:
844:
833:
826:
820:
767:
755:
745:
738:
730:
711:
708:
538:
536:-bit number
532:
518:
511:
507:
501:
494:
484:
482:-bit number
478:
467:
447:
440:
430:
427:
406:
388:
384:
377:
373:
357:
353:
346:
337:
311:
305:
295:
291:
285:
281:
277:
269:
242:
231:
204:
189:
157:cryptography
142:
107:
98:
79:prime number
58:
52:
4007:Extravagant
4002:Equidigital
3963:Untouchable
3883:Semiperfect
3863:Hemiperfect
3792:Square-free
3493:Pollard rho
3450:Goldschmidt
3184:Pocklington
3174:BaillieâPSW
2954:RSA problem
2523:p. 583
1715:, for some
1377:denoted by
1364:class group
1107:RSA numbers
961:) with the
830:besides 1?
727:takes only
719:, however,
522:, that is,
399:18848997157
325:18848997161
207:RSA problem
169:mathematics
145:non-quantum
130:square root
55:mathematics
4098:Categories
4043:Arithmetic
4036:Other sets
3995:-dependent
3605:Cornacchia
3600:Chakravala
3148:algorithms
2959:Strong RSA
2949:Phi-hiding
2741:References
2543:Stan Wagon
2191:2022-06-22
1705:= 5, ...,
1584:(log|
1517:generators
1470:Denote by
1327:L-notation
1090:Category 2
1047:Williams'
1036:Pollard's
996:Category 1
721:Peter Shor
436:semiprimes
428:Among the
422:See also:
402:â = 137292
215:public-key
192:semiprimes
153:difficulty
4073:Descartes
4048:Deficient
3983:Betrothed
3888:Practical
3777:Semiprime
3772:Composite
3579:Berlekamp
3536:Euclidean
3424:Euclidean
3404:ToomâCook
3399:Karatsuba
2371:1887/2149
2339:215746906
1995:in which
1907:Δ
1899:∈
1892:∏
1847:∈
1840:∏
1679:Take the
1454:forms in
1296:
1290:
1275:
1099:Kraitchik
1054:algorithm
1043:algorithm
743:space on
735:time and
667:
661:
630:
556:
542:in time:
470:algorithm
454:Xeon Gold
149:algorithm
4058:Solitary
4053:Friendly
3978:Sociable
3968:Amicable
3956:-related
3909:Abundant
3807:Achilles
3797:Powerful
3710:Overview
3546:Lehmer's
3440:Chunking
3427:division
3356:Fermat's
3040:Lattices
3014:Pairings
2869:download
2801:(2013).
2754:(2001).
2545:(2000).
2498:(eds.),
2443:11780055
2386:12 March
2256:(2011),
2102:See also
1811: :
1668:, where
1442:, where
1333:and the
1323:little-o
1146:(SQUFOF)
1113:method.
488:in time
327:, where
280:= 171 Ă
163:and the
159:such as
4063:Sublime
4017:Harshad
3843:Perfect
3827:Unusual
3817:Regular
3787:Sphenic
3722:Divisor
3662:Italics
3584:Kunerth
3564:Cipolla
3445:Fourier
3414:FĂŒrer's
3308:Euler's
3298:Dixon's
3221:PĂ©pin's
2730:1137100
2649:0878705
2604:0657269
2518:2467561
2451:4400832
2423:Bibcode
2331:2500087
2286:2789493
2051:2-Sylow
1769:
1755:
1588:|)
1507:
1493:
1125:(CFRAC)
869:
853:
818:, does
450:RSA-250
443:RSA-240
412:1372933
397:√
364:√
351:√
335:√
321:1372933
257:Testing
243:By the
213:-based
71:factors
67:product
65:into a
4012:Frugal
3972:Triple
3812:Smooth
3782:Pronic
3644:Schoof
3531:Binary
3435:Binary
3371:Shor's
3189:Fermat
2858:msieve
2840:
2811:
2790:
2762:
2728:
2647:
2602:
2561:
2555:168â69
2516:
2506:
2449:
2441:
2404:Nature
2377:
2337:
2329:
2319:
2284:
2274:
2182:
2053:group
1997:Î = â4
1452:smooth
1103:family
1056:, and
905:. The
771:
323:, and
289:where
183:, and
89:, but
4027:Smith
3944:Weird
3822:Rough
3767:Prime
3465:Short
3194:Lucas
2704:(PDF)
2667:(PDF)
2447:S2CID
2413:arXiv
2335:S2CID
2228:(PDF)
2149:Notes
2020:Î = (
1748:with
1698:= 3,
1691:= 2,
1663:Î = â
1548:with
1483:with
1437:Î = â
1096:, or
873:with
840:co-NP
317:13729
294:<
238:2 Ă 3
234:= 864
3993:Base
3460:Long
3394:Long
2838:ISBN
2809:ISBN
2788:ISBN
2760:ISBN
2750:and
2559:ISBN
2541:and
2504:ISBN
2439:PMID
2388:2021
2375:ISBN
2317:ISBN
2272:ISBN
2180:ISBN
2004:Î =
1800:and
1728:Let
1657:Let
1648:Let
1325:and
838:and
798:and
404:for
382:and
196:bits
171:and
3624:LLL
3470:SRT
3329:+ 1
3321:â 1
3169:APR
3164:AKS
3061:gap
3051:gap
2716:doi
2679:doi
2635:doi
2592:doi
2431:doi
2409:414
2367:hdl
2359:doi
2309:doi
2264:doi
2236:doi
2172:doi
2066:(Î)
2061:of
2059:(Î)
2055:Sll
2032:+ 2
2024:â 2
2018:or
2012:â 4
2002:or
1784:of
1775:= 1
1639:gcd
1606:of
1552:in
1539:of
1519:of
1513:= 1
1370:of
1321:in
1293:log
1287:log
1272:log
1052:+ 1
1041:â 1
998:or
975:RSA
915:BQP
751:NMR
664:log
658:log
627:log
553:exp
468:No
369:= 2
255:.)
236:as
211:RSA
132:of
53:In
4100::
3628:KZ
3626:;
2833:-
2776:.
2726:MR
2724:.
2710:.
2706:.
2691:^
2675:50
2673:.
2669:.
2645:MR
2643:.
2631:48
2629:.
2625:.
2600:MR
2598:.
2586:.
2582:.
2557:.
2530:^
2514:MR
2512:,
2494:;
2490:;
2482:;
2445:.
2437:.
2429:.
2421:.
2407:.
2373:.
2365:.
2333:,
2327:MR
2325:,
2315:,
2282:MR
2280:,
2270:,
2178:,
2098:.
2077:.
2028:)(
1999:ac
1983:â
1972:,
1968:,
1946:1.
1815:â
1720:â
1665:dn
1599:.
1439:dn
1435:,
1405:,
1401:,
1386:.
1345:.
1092:,
1045:,
911:UP
878:â€
847:=
836:NP
764:.
737:O(
729:O(
514:))
414:.
387:+
376:â
362:=
356:â
349:=
319:,
284:Ă
187:.
179:,
124:,
120:,
105:.
83:15
57:,
3974:)
3970:(
3697:e
3690:t
3683:v
3630:)
3622:(
3327:p
3319:p
3137:e
3130:t
3123:v
3063:)
3059:(
3053:)
3049:(
2922:e
2915:t
2908:v
2846:.
2819:.
2817:.
2768:.
2732:.
2718::
2712:5
2685:.
2681::
2651:.
2637::
2594::
2588:3
2567:.
2525:.
2468:.
2453:.
2433::
2425::
2415::
2390:.
2369::
2361::
2311::
2266::
2242:.
2238::
2174::
2135:p
2094:n
2092:L
2068:.
2064:G
2057:2
2047:n
2043:n
2038:.
2036:)
2034:a
2030:b
2026:a
2022:b
2016:)
2014:c
2010:a
2008:(
2006:a
1993:Î
1988:Î
1985:G
1981:f
1976:)
1974:c
1970:b
1966:a
1964:(
1943:=
1939:)
1933:)
1930:q
1927:(
1924:t
1919:q
1915:f
1903:P
1896:q
1887:(
1883:.
1879:)
1873:)
1870:x
1867:(
1864:r
1860:x
1851:X
1844:x
1835:(
1822:}
1820:Î
1817:P
1813:q
1808:q
1804:f
1802:{
1798:X
1793:.
1790:Î
1787:G
1782:X
1777:.
1773:)
1765:q
1761:/
1758:Î
1751:(
1745:Î
1742:G
1735:q
1731:f
1725:.
1722:N
1718:t
1711:t
1707:p
1703:3
1700:p
1696:2
1693:p
1689:1
1686:p
1681:t
1674:Î
1670:d
1659:Î
1650:n
1643:n
1635:Î
1630:Î
1627:G
1621:Î
1618:G
1612:Î
1609:G
1596:0
1593:c
1586:Î
1582:0
1579:c
1574:q
1568:q
1564:f
1558:Î
1555:P
1550:q
1545:Î
1542:G
1535:q
1531:f
1525:Î
1522:G
1511:)
1503:q
1499:/
1496:Î
1489:(
1481:q
1476:Î
1473:P
1465:d
1460:Î
1457:G
1448:d
1444:d
1433:n
1429:Î
1425:n
1421:n
1409:)
1407:c
1403:b
1399:a
1397:(
1392:Î
1389:G
1383:Î
1380:G
1375:Î
1358:n
1356:L
1302:)
1299:n
1284:(
1281:)
1278:n
1269:(
1264:)
1261:)
1258:1
1255:(
1252:o
1249:+
1246:1
1243:(
1239:e
1235:=
1231:]
1227:)
1224:1
1221:(
1218:o
1215:+
1212:1
1209:,
1203:2
1200:1
1193:[
1187:n
1183:L
1050:p
1039:p
958:n
952:b
946:n
940:n
934:n
902:n
892:k
886:n
880:k
876:d
871:)
865:d
861:/
857:n
851:(
849:d
845:n
827:k
821:n
806:k
786:n
746:b
741:)
739:b
733:)
731:b
712:n
694:.
690:)
683:3
680:2
674:)
670:n
654:(
646:3
643:1
637:)
633:n
623:(
617:)
613:)
610:1
607:(
604:o
601:+
595:3
592:2
586:)
580:3
577:8
571:(
565:(
560:(
539:n
533:b
519:Δ
512:Δ
502:k
497:)
495:b
493:(
491:O
485:n
479:b
431:b
407:a
395:â
389:b
385:a
378:b
374:a
366:4
358:n
354:a
347:b
338:n
333:â
312:n
306:p
296:q
292:p
286:q
282:p
278:n
232:n
134:n
126:5
122:3
118:2
110:n
91:7
41::
34:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.