Don't take life too seriously: it's just a temporary situation

Pseudoprimi forti di Fermat

Teoria dei numeri 

Rappresentiamo un numero naturale dispari p come 2nr + 1 con r dispari; se p è primo rispetto a b e divide bp – 1 – 1, è primo o pseudoprimo di Fermat in base b. Se p è primo, deve dividere almeno uno dei numeri br – 1, br + 1, b2r + 1, b4r + 1, … b^(2^(n – 1) * r) + 1 = b^((p – 1) / 2) + 1; se divide uno di questi numeri, senza essere primo, si dice “pseudoprimo forte di Fermat” o più semplicemente “pseudoprimo forte” in base b.

Più formalmente, un numero composto p, primo rispetto a b e della forma 2nr + 1 con r dispari è pseudoprimo forte di Fermat in base b se br ≡ 1 mod p o b2mr ≡ –1 mod p, per un valore di m tra 0 e n – 1.

 

Dalla definizione segue che tutti gli pseudoprimi forti di Fermat rispetto a una base sono anche pseudoprimi di Fermat e pseudoprimi di Eulero (I) rispetto alla stessa base.

 

Non tutti gli pseudoprimi di Fermat sono pseudoprimi forti di Fermat; per esempio, 561 è un numero di Carmichael, ossia pseudoprimo di Fermat in qualsiasi base, e 2560 ≡ 1 mod 561, ma non è uno pseudoprimo forte di Fermat in base 2, perché 561 = 2435 + 1, ma 2280 ≡ 1 mod 561, 2140 ≡ 67 mod 561, 270 ≡ 166 mod 561 e 235 ≡ 263 mod 561.

Invece 561 è pseudoprimo forte di Fermat in base 50, perché 5035 ≡ –1 mod 561.

 

Per ogni base esistono infiniti pseudoprimi forti di Fermat, come dimostrarono Carl Pomerance, J.L. Selfridge e Simon S. Wagstaff Jr. nel 1980, tuttavia nessun numero composto è pseudoprimo forte di Fermat in tutte le basi: tra essi non esiste un equivalente dei numeri di Carmichael o degli pseudoprimi assoluti di Eulero.

 

Il test di primalità di Miller – Rabin (v. numeri primi) si basa sul verificare se un numero è pseudoprimo forte di Fermat rispetto a varie basi: scegliendo n basi a caso, la probabilità che un numero composto superi l’esame è minore di 4n e aumentando il numero delle basi, si riduce a piacere la probabilità di errore.

Le basi tuttavia devono essere scelte a caso e non sequenzialmente, perché per esempio 9 è pseudoprimo forte di Fermat in 7 basi prime fino a 101 (v. la tabella più avanti) e François Arnault dimostrò nel 1994 che:

  • se p, q e r sono primi, con p ≡ 872443 mod 4924920, q = 13(p – 1) + 1 e r = 41(q – 1) + 1, pqr è un numero di Carmichael e pseudoprimo forte di Fermat rispetto alle basi 2, 3, 5 e 7;

  • se p, q, r, s e t sono primi, con p ≡ 14354973403 mod 26363096760, q = 13(p – 1) + 1, r = 41(q – 1) + 1, s = 53(r – 1) + 1 e t = 101(s – 1) + 1, pqrst è un numero di Carmichael e pseudoprimo forte di Fermat rispetto alle basi 2, 3, 5, 7 e 11;

  • il numero di 397 cifre p(313(p – 1) + 1)(353(p – 1) + 1), dove p è il numero primo 29674495668685510550154174642905332730771991799853043350995075531276838753171770199594238596428121188033664754218345562493168782883, è pseudoprimo forte di Fermat rispetto a tutte le basi minori di 307.

 

Nel 1994 R. Alford, A. Granville e Carl Pomerance dimostrarono che per ogni insieme finito di basi esiste un insieme infinito di numeri di Carichael che sono pseudoprimi forti di Fermat rispetto a tutte le basi dell’insieme.

 

Se un intero è pseudoprimo forte di Fermat rispetto a una base, lo è anche rispetto alle potenze della base. L’inverso non è sempre vero, uno pseudoprimo forte di Fermat rispetto a una potenza non è detto che sia tale rispetto alla base; per esempio, 341 è pseudoprimo forte di Fermat in base 4 = 22, ma non in base 2.

Se un intero è pseudoprimo forte di Fermat rispetto a due basi, lo è anche rispetto al loro prodotto. L’inverso non è sempre vero, ossia uno pseudoprimo forte di Fermat rispetto a un numero composto non è detto che lo sia rispetto ai fattori; per esempio, 217 è pseudoprimo forte di Fermat in base 6 = 2 • 3, ma non lo è in base 2 o 3.

 

Dato che kn + 1 ≡ 1 mod n e, se n è dispari, (k * n + 1)^((n – 1) / 2) ≡ 1 mod n, quindi ogni intero composto dispari n è pseudoprimo forte di Fermat in base kn + 1 per ogni intero positivo k e in particolare in base n + 1.

Dato che kn – 1 ≡ –1 mod n, se n è dispari e 2m è la massima potenza di 2 che divide n – 1, (k * n – 1)^((n – 1) / 2^m) ≡ ±1 mod n, quindi ogni intero composto dispari n è pseudoprimo forte di Fermat in base kn – 1 per ogni intero positivo k e in particolare in base n – 1.

Di conseguenza ogni intero composto dispari n è pseudoprimo forte di Fermat in tutte le basi della forma (an + 1)r(bn – 1)s.

 

Un intero dispari n può essere pseudoprimo forte di Fermat rispetto al massimo a (n – 1) / 4 basi minori di n (Donald Erwin Knuth, 1981).

Il numero di basi rispetto alle quali un intero dispari n è pseudoprimo forte di Fermat è Numero di basi rispetto alle quali n è pseudoprimo forte di Fermat, dove n* è il massimo divisore dispari di n – 1 (per la definizione di e(n) v. pseudoprimi di Eulero – Jacobi).

 

Un numero che è pseudoprimo forte di Fermat in parecchie basi è probabilmente un numero primo e questo fornisce un ottimo test per decidere se un numero è primo o composto, anche se la risposta è certa solo se il test indica che il numero è composto o se il numero è relativamente piccolo. La tabella seguente riporta il minimo pseudoprimo forte di Fermat alcune basi.

Basi

Minimo pseudoprimo forte di Fermat

Scopritore e anno

2

2047

Carl Pomerance, J.L. Selfridge e Simon S. Wagstaff Jr.

2, 3

1373653

Carl Pomerance, J.L. Selfridge e Simon S. Wagstaff Jr.

2, 3, 5

25326001

Carl Pomerance, J.L. Selfridge e Simon S. Wagstaff Jr.

2, 3, 5, 7

3215031751

Carl Pomerance, J.L. Selfridge e Simon S. Wagstaff Jr.

2, 3, 5, 7, 11

2152302898747

G. Jaeschke, 1993

2, 3, 5, 7, 11, 13

3474749660383

G. Jaeschke, 1993

2, 3, 5, 7, 11, 13, 17

341550071728321

G. Jaeschke, 1993

2, 3, 5, 7, 11, 13, 17, 19

341550071728321

G. Jaeschke, 1993

2, 3, 5, 7, 11, 13, 17, 19, 23

3825123056546413051

Yupeng Jiang e Yingpu Deng, 2012

2, 3, 5, 7, 11, 13, 17, 19, 23, 29

3825123056546413051

Yupeng Jiang e Yingpu Deng, 2012

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31

3825123056546413051

Yupeng Jiang e Yingpu Deng, 2012

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37

318665857834031151167461

Jonathan P. Sorenson, Jonathan Webster, 2015

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41

3317044064679887385961981

Jonathan P. Sorenson, Jonathan Webster, 2015

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43

≤ 6003094289670105800312596501

Zhenxiang Zhang, 2007

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

≤ 59276361075595573263446330101

Zhenxiang Zhang, 2007

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53

≤ 564132928021909221014087501701

Zhenxiang Zhang, 2007

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59

≤ 564132928021909221014087501701

Zhenxiang Zhang, 2007

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61

≤ 1543267864443420616877677640751301

Zhenxiang Zhang, 2007

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67

≤ 1543267864443420616877677640751301

Zhenxiang Zhang, 2007

31, 73

9080191

G. Jaeschke, 1993

350, 3958281543

170584961

Steve Worley

2, 7, 61

4759123141

G. Jaeschke, 1993

2, 379215, 457083754

75792980677

G. Jaeschke, 1993

2, 3, 5, 408625

736775510329

G. Jaeschke, 1993

2, 1215, 34862, 574237825

21652684502221

G. Jaeschke, 1993

 

Il minimo pseudoprimo forte di Fermat rispetto a 2 e 3 con 3 fattori primi è 101649241.

L’unico pseudoprimo forte di Fermat rispetto a 2, 3, 5 e 7 inferiore a 118670087467 è 3215031751 (G. Jaeschke, 1993).

Gli pseudoprimi forti di Fermat rispetto a 2, 3 e 5 inferiori a 1011 sono: 25326001, 161304001, 960946321, 1157839381, 3215031751, 3697278427, 5764643587, 6770862367, 14386156093, 15579919981, 18459366157, 19887974881, 21276028621, 27716349961, 29118033181, 37131467521, 41752650241, 42550716781, 43536545821, 44732778751, 44778481441, 48354810571, 52139147581, 53700690781, 56209415767, 57698562127, 67403434561, 73796984161, 74190097801, 75285070351, 75350936251, 77475820141, 79696887661, 83828294551, 88473676747, 88974090367, 98515393021.

Qui trovate gli pseudoprimi forti di Fermat in base 2, 3 e 5 minori di 1016 (Rick L. Shepherd e Charles R. Greathouse IV, The Online Encyclopedia of Integer Sequences http://oeis.org).

Gli pseudoprimi forti di Fermat rispetto a 2, 3, 5 e 7 inferiori a 1013 sono: 3215031751, 118670087467, 307768373641, 315962312077, 354864744877, 457453568161, 528929554561, 546348519181, 602248359169, 1362242655901, 1871186716981, 2152302898747, 2273312197621, 2366338900801, 3343433905957, 3461715915661, 3474749660383, 3477707481751, 4341937413061, 4777422165601, 5537838510751, 5792018372251, 6597606223981, 8006855187361.

Qui trovate gli pseudoprimi forti di Fermat in base 2, 3, 5 e 7 minori di 264 (Rick L. Shepherd e Charles R. Greathouse IV, The Online Encyclopedia of Integer Sequences http://oeis.org).

 

Tabelle del genere permettono di verificare se un intero non troppo grande è primo con poche centinaia di operazioni aritmetiche. Per esempio, per determinare se un numero fino a 1013 è primo, il metodo più veloce è verificare se è pseudoprimo forte di Fermat in base 2, 3, 5 e 7 e in caso affermativo controllare se è nella lista. Oppure per determinare se un numero fino a 1033 è primo, il metodo più veloce è verificare se è pseudoprimo forte di Fermat nelle 18 basi prime fino a 61.

 

Se l’ipotesi di Riemann generalizzata è vera, come tutti credono, e un intero n è pseudoprimo forte di Fermat rispetto a tutte le basi minori di 2log2n, allora è primo. Questo fornirebbe un test molto efficiente per decidere se un intero molto grande ia primo; per ora però dobbiamo accontentarci di una risposta “molto probabile”.

 

Riguardo alla distribuzione degli pseudoprimi forti di Fermat, sappiamo che il numero di pseudoprimi forti di Fermat in base a minori di n è maggiore di log(n) / (4 * a * log(a)), per n maggiore di a15a (Carl Pomerance, J.L. Selfridge e Samuel S. Wagstaff Jr., 1980) e non supera e^(log(n)^(5 / 14)) (Carl Pomerance, 1982).

 

Rotkiewicz e van der Poorten dimostrarono nel 1980 che anche per gli pseudoprimi forti di Fermat vale un analogo del teorema di Dirichlet: ogni progressione aritmetica del tipo an + b, con a e b primi tra loro, contiene infiniti pseudoprimi forti di Fermat in ogni base.

 

Tutti gli pseudoprimi forti di Fermat rispetto a una base sono anche pseudoprimi di Eulero – Jacobi rispetto alla stessa base, come dimostrò J.L. Selfridge; il viceversa vale sempre se lo pseudoprimo diviso per 4 dà resto 3 (Malm, 1977) oppure se la base non è residuo quadratico modulo lo pseudoprimo (Carl Pomerance, J.L. Selfridge e Samuel S. Wagstaff Jr., 1980).

 

La tabella seguente mostra gli pseudoprimi forti di Fermat minori di 105 nelle basi fino a 20.

Base

Pseudoprimi forti di Fermat

2

2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633, 65281, 74665, 80581, 85489, 88357, 90751

3

121, 703, 1891, 3281, 8401, 8911, 10585, 12403, 16531, 18721, 19345, 23521, 31621, 44287, 47197, 55969, 63139, 74593, 79003, 82513, 87913, 88573, 97567

4

341, 1387, 2047, 3277, 4033, 4371, 4681, 5461, 8321, 8911, 10261, 13747, 14491, 15709, 15841, 19951, 29341, 31621, 42799, 49141, 49981, 52633, 60787, 65077, 65281, 74665, 80581, 83333, 85489, 88357, 90751

5

781, 1541, 5461, 5611, 7813, 13021, 14981, 15751, 24211, 25351, 29539, 38081, 40501, 44801, 53971, 79381

6

217, 481, 1111, 1261, 2701, 3589, 5713, 6533, 11041, 14701, 20017, 29341, 34441, 39493, 43621, 46657, 46873, 49141, 49661, 58969, 74023, 74563, 76921, 83333, 87061, 92053, 94657, 94697, 97751, 97921

7

25, 325, 703, 2101, 2353, 4525, 11041, 14089, 20197, 29857, 29891, 39331, 49241, 58825, 64681, 76627, 78937, 79381, 87673, 88399, 88831

8

9, 65, 481, 511, 1417, 2047, 2501, 3277, 3641, 4033, 4097, 4681, 8321, 11041, 15841, 16589, 19561, 24311, 24929, 29341, 41441, 42799, 45761, 49141, 52429, 52633, 54161, 55969, 56033, 59291, 61337, 65281, 66197, 74023, 74665, 77161, 80581, 85489, 87061, 88357, 90751, 94657, 95281, 97921

9

91, 121, 671, 703, 1541, 1729, 1891, 2821, 3281, 3367, 3751, 5551, 7381, 8401, 8911, 10585, 11011, 12403, 14383, 15203, 16471, 16531, 18721, 19345, 23521, 24661, 24727, 28009, 29341, 30857, 31621, 32791, 38503, 44287, 46999, 47197, 49051, 49141, 53131, 55969, 63139, 63973, 68887, 74593, 76627, 79003, 82513, 83333, 87913, 88573, 88831, 90751, 93961, 96139, 97567

10

9, 91, 1729, 4187, 6533, 8149, 8401, 10001, 11111, 19201, 21931, 50851, 79003, 83119, 94139

11

133, 793, 2047, 4577, 5041, 12403, 13333, 14521, 17711, 23377, 43213, 43739, 47611, 48283, 49601, 50737, 50997, 56057, 58969, 68137, 74089, 85879, 86347, 87913, 88831

12

91, 133, 145, 247, 1649, 1729, 2821, 8911, 9073, 10585, 13051, 13333, 16471, 19517, 20737, 21361, 24013, 24727, 26467, 29539, 31483, 31621, 34219, 34861, 35881, 38311, 38503, 40321, 53083, 67861, 79381, 79501, 88831, 97351

13

85, 1099, 5149, 7107, 8911, 9637, 13019, 14491, 17803, 19757, 20881, 22177, 23521, 26521, 35371, 44173, 45629, 54097, 56033, 57205, 75241, 83333, 85285, 86347

14

15, 841, 2743, 3277, 5713, 6541, 7171, 9073, 18721, 21667, 22261, 23521, 38221, 38417, 40501, 41371, 49471, 58255, 68401, 71969, 79003, 88381, 91681, 95033, 96049, 97469

15

1687, 3277, 6541, 14041, 14701, 15409, 25313, 31021, 47461, 49241, 50401, 54241, 58969, 60691, 82733, 88831, 97921

16

15, 91, 341, 435, 451, 645, 703, 1247, 1271, 1387, 1695, 1729, 1891, 1905, 2047, 2071, 2701, 2821, 3277, 3367, 3683, 4033, 4371, 4681, 4795, 4859, 5461, 5551, 6601, 6643, 7957, 8321, 8695, 8911, 9131, 9211, 9919, 10261, 10585, 12403, 13019, 13741, 13747, 13981, 14351, 14491, 15051, 15211, 15709, 15841, 16471, 18705, 19951, 20191, 24727, 25351, 25761, 26335, 26599, 27511, 29341, 30121, 31621, 33227, 33355, 35333, 38503, 40951, 41041, 42127, 42799, 45551, 45991, 47611, 48599, 49141, 49155, 49981, 51319, 52633, 53131, 55245, 57421, 60701, 60787, 61447, 62745, 63973, 65077, 65281, 68101, 68251, 72631, 72885, 73555, 74563, 74665, 76627, 77879, 79003, 80581, 81631, 81915, 83333, 85489, 87249, 88357, 88831, 90751, 98671

17

9, 91, 145, 781, 1111, 2821, 4033, 4187, 5365, 5833, 6697, 7171, 15805, 19729, 21781, 22791, 24211, 26245, 31621, 33001, 33227, 34441, 35371, 38081, 42127, 49771, 71071, 74665, 77293, 78881, 88831, 96433, 97921, 98671

18

25, 49, 65, 325, 343, 1369, 1387, 2977, 4577, 5725, 5833, 5941, 6601, 11425, 12025, 18631, 22411, 28153, 29341, 30889, 35425, 39817, 40501, 41159, 49141, 60685, 60691, 74425, 80137, 90751, 99451

19

9, 49, 169, 343, 1849, 2353, 2701, 4033, 4681, 6541, 6697, 7957, 9997, 12403, 13213, 13747, 15251, 16531, 18769, 19729, 24761, 30589, 31621, 31861, 32477, 41003, 49771, 63139, 64681, 65161, 66421, 68257, 73555, 96049

20

21, 671, 889, 1891, 2059, 2761, 5461, 7999, 13051, 15311, 16441, 21667, 25681, 34861, 37901, 38989, 42127, 49771, 50737, 54811, 64681, 68251, 78961, 85591, 88831, 92509, 93031, 96049, 97921

 

 

Se n è pseudoprimo di Fermat in base 2, 2n – 1 è pseudoprimo forte di Fermat in base 2.

Tutti i numeri di Mersenne composti Mp con p primo e tutti i numeri di Fermat composti sono pseudoprimi forti di Fermat in base 2.

 

La tabella seguente mostra il numero di pseudoprimi di vari tipi in base 2 minori di 10n, per n fino a 19 (Jan Feitsma, William F. Galway, Carl Pomerance, John L. Selfridge, Samuel S. Wagstaff, Eric W. Weisstein, The Online Encyclopedia of Integer Sequences http://oeis.org).

n

Pseudoprimi

Pseudoprimi di Eulero – Jacobi

Pseudoprimi forti di Fermat

10

0

0

0

102

0

0

0

103

3

1

0

104

22

12

5

105

78

36

16

106

245

114

43

107

750

375

105

108

2057

1071

255

109

5597

2939

646

1010

14887

7706

1547

1011

38975

20417

8607

1012

101629

53332

22407

1013

264239

139597

 

1014

687007

364217

 

1015

1801533

957111

 

1016

4744920

2526795

 

1017

12604009

6725234

 

1018

33763684

18069359

 

1019

91210364

48961462

 

 

In base 2:

  • il minimo pseudoprimo forte di Fermat che sia multiplo di 3 è 5455590801;

  • il minimo pseudoprimo forte di Fermat che sia prodotto di due pseudoprimi forti di Fermat è 13216141 = 3277 · 4033;

  • Il minimo pseudoprimo forte di Fermat, che sia prodotto di tre primi, tali che il prodotto di due qualsiasi di essi sia uno pseudoprimo forte di Fermat è 13421773 = 53 · 157 · 1613.

 

La tabella seguente mostra il minimo pseudoprimo forte di Fermat nelle basi fino a 100.

Base

Minimo pseudoprimo forte di Fermat

1

9

2

2047

3

121

4

341

5

781

6

217

7

25

8

9

9

91

10

9

11

133

12

91

13

85

14

15

15

1687

16

15

17

9

18

25

19

9

20

21

21

221

22

21

23

169

24

25

25

217

26

9

27

121

28

9

29

15

30

49

31

15

32

25

33

545

34

33

35

9

36

35

37

9

38

39

39

133

40

39

41

21

42

451

43

21

44

9

45

481

46

9

47

65

48

49

49

25

50

49

51

25

52

51

53

9

54

55

55

9

56

55

57

25

58

57

59

15

60

481

61

15

62

9

63

529

64

9

65

33

66

65

67

33

68

25

69

35

70

69

71

9

72

85

73

9

74

15

75

91

76

15

77

39

78

77

79

39

80

9

81

91

82

9

83

21

84

85

85

21

86

85

87

247

88

87

89

9

90

91

91

9

92

91

93

25

94

93

95

1891

96

95

97

49

98

9

99

25

100

9

 

La tabella seguente mostra per i numeri composti dispari minori di 100 le basi minori di 1000 nelle quali sono pseudoprimi forti di Fermat.

Numero

Basi

9

8, 10, 17, 19, 26, 28, 35, 37, 44, 46, 53, 55, 62, 64, 71, 73, 80, 82, 89, 91, 98, 100, 107, 109, 116, 118, 125, 127, 134, 136, 143, 145, 152, 154, 161, 163, 170, 172, 179, 181, 188, 190, 197, 199, 206, 208, 215, 217, 224, 226, 233, 235, 242, 244, 251, 253, 260, 262, 269, 271, 278, 280, 287, 289, 296, 298, 305, 307, 314, 316, 323, 325, 332, 334, 341, 343, 350, 352, 359, 361, 368, 370, 377, 379, 386, 388, 395, 397, 404, 406, 413, 415, 422, 424, 431, 433, 440, 442, 449, 451, 458, 460, 467, 469, 476, 478, 485, 487, 494, 496, 503, 505, 512, 514, 521, 523, 530, 532, 539, 541, 548, 550, 557, 559, 566, 568, 575, 577, 584, 586, 593, 595, 602, 604, 611, 613, 620, 622, 629, 631, 638, 640, 647, 649, 656, 658, 665, 667, 674, 676, 683, 685, 692, 694, 701, 703, 710, 712, 719, 721, 728, 730, 737, 739, 746, 748, 755, 757, 764, 766, 773, 775, 782, 784, 791, 793, 800, 802, 809, 811, 818, 820, 827, 829, 836, 838, 845, 847, 854, 856, 863, 865, 872, 874, 881, 883, 890, 892, 899, 901, 908, 910, 917, 919, 926, 928, 935, 937, 944, 946, 953, 955, 962, 964, 971, 973, 980, 982, 989, 991, 998, 1000

15

14, 16, 29, 31, 44, 46, 59, 61, 74, 76, 89, 91, 104, 106, 119, 121, 134, 136, 149, 151, 164, 166, 179, 181, 194, 196, 209, 211, 224, 226, 239, 241, 254, 256, 269, 271, 284, 286, 299, 301, 314, 316, 329, 331, 344, 346, 359, 361, 374, 376, 389, 391, 404, 406, 419, 421, 434, 436, 449, 451, 464, 466, 479, 481, 494, 496, 509, 511, 524, 526, 539, 541, 554, 556, 569, 571, 584, 586, 599, 601, 614, 616, 629, 631, 644, 646, 659, 661, 674, 676, 689, 691, 704, 706, 719, 721, 734, 736, 749, 751, 764, 766, 779, 781, 794, 796, 809, 811, 824, 826, 839, 841, 854, 856, 869, 871, 884, 886, 899, 901, 914, 916, 929, 931, 944, 946, 959, 961, 974, 976, 989, 991

21

20, 22, 41, 43, 62, 64, 83, 85, 104, 106, 125, 127, 146, 148, 167, 169, 188, 190, 209, 211, 230, 232, 251, 253, 272, 274, 293, 295, 314, 316, 335, 337, 356, 358, 377, 379, 398, 400, 419, 421, 440, 442, 461, 463, 482, 484, 503, 505, 524, 526, 545, 547, 566, 568, 587, 589, 608, 610, 629, 631, 650, 652, 671, 673, 692, 694, 713, 715, 734, 736, 755, 757, 776, 778, 797, 799, 818, 820, 839, 841, 860, 862, 881, 883, 902, 904, 923, 925, 944, 946, 965, 967, 986, 988

25

7, 18, 24, 26, 32, 43, 49, 51, 57, 68, 74, 76, 82, 93, 99, 101, 107, 118, 124, 126, 132, 143, 149, 151, 157, 168, 174, 176, 182, 193, 199, 201, 207, 218, 224, 226, 232, 243, 249, 251, 257, 268, 274, 276, 282, 293, 299, 301, 307, 318, 324, 326, 332, 343, 349, 351, 357, 368, 374, 376, 382, 393, 399, 401, 407, 418, 424, 426, 432, 443, 449, 451, 457, 468, 474, 476, 482, 493, 499, 501, 507, 518, 524, 526, 532, 543, 549, 551, 557, 568, 574, 576, 582, 593, 599, 601, 607, 618, 624, 626, 632, 643, 649, 651, 657, 668, 674, 676, 682, 693, 699, 701, 707, 718, 724, 726, 732, 743, 749, 751, 757, 768, 774, 776, 782, 793, 799, 801, 807, 818, 824, 826, 832, 843, 849, 851, 857, 868, 874, 876, 882, 893, 899, 901, 907, 918, 924, 926, 932, 943, 949, 951, 957, 968, 974, 976, 982, 993, 999

27

26, 28, 53, 55, 80, 82, 107, 109, 134, 136, 161, 163, 188, 190, 215, 217, 242, 244, 269, 271, 296, 298, 323, 325, 350, 352, 377, 379, 404, 406, 431, 433, 458, 460, 485, 487, 512, 514, 539, 541, 566, 568, 593, 595, 620, 622, 647, 649, 674, 676, 701, 703, 728, 730, 755, 757, 782, 784, 809, 811, 836, 838, 863, 865, 890, 892, 917, 919, 944, 946, 971, 973, 998, 1000

33

32, 34, 65, 67, 98, 100, 131, 133, 164, 166, 197, 199, 230, 232, 263, 265, 296, 298, 329, 331, 362, 364, 395, 397, 428, 430, 461, 463, 494, 496, 527, 529, 560, 562, 593, 595, 626, 628, 659, 661, 692, 694, 725, 727, 758, 760, 791, 793, 824, 826, 857, 859, 890, 892, 923, 925, 956, 958, 989, 991

35

34, 36, 69, 71, 104, 106, 139, 141, 174, 176, 209, 211, 244, 246, 279, 281, 314, 316, 349, 351, 384, 386, 419, 421, 454, 456, 489, 491, 524, 526, 559, 561, 594, 596, 629, 631, 664, 666, 699, 701, 734, 736, 769, 771, 804, 806, 839, 841, 874, 876, 909, 911, 944, 946, 979, 981

39

38, 40, 77, 79, 116, 118, 155, 157, 194, 196, 233, 235, 272, 274, 311, 313, 350, 352, 389, 391, 428, 430, 467, 469, 506, 508, 545, 547, 584, 586, 623, 625, 662, 664, 701, 703, 740, 742, 779, 781, 818, 820, 857, 859, 896, 898, 935, 937, 974, 976

45

44, 46, 89, 91, 134, 136, 179, 181, 224, 226, 269, 271, 314, 316, 359, 361, 404, 406, 449, 451, 494, 496, 539, 541, 584, 586, 629, 631, 674, 676, 719, 721, 764, 766, 809, 811, 854, 856, 899, 901, 944, 946, 989, 991

49

18, 19, 30, 31, 48, 50, 67, 68, 79, 80, 97, 99, 116, 117, 128, 129, 146, 148, 165, 166, 177, 178, 195, 197, 214, 215, 226, 227, 244, 246, 263, 264, 275, 276, 293, 295, 312, 313, 324, 325, 342, 344, 361, 362, 373, 374, 391, 393, 410, 411, 422, 423, 440, 442, 459, 460, 471, 472, 489, 491, 508, 509, 520, 521, 538, 540, 557, 558, 569, 570, 587, 589, 606, 607, 618, 619, 636, 638, 655, 656, 667, 668, 685, 687, 704, 705, 716, 717, 734, 736, 753, 754, 765, 766, 783, 785, 802, 803, 814, 815, 832, 834, 851, 852, 863, 864, 881, 883, 900, 901, 912, 913, 930, 932, 949, 950, 961, 962, 979, 981, 998, 999

51

50, 52, 101, 103, 152, 154, 203, 205, 254, 256, 305, 307, 356, 358, 407, 409, 458, 460, 509, 511, 560, 562, 611, 613, 662, 664, 713, 715, 764, 766, 815, 817, 866, 868, 917, 919, 968, 970

55

54, 56, 109, 111, 164, 166, 219, 221, 274, 276, 329, 331, 384, 386, 439, 441, 494, 496, 549, 551, 604, 606, 659, 661, 714, 716, 769, 771, 824, 826, 879, 881, 934, 936, 989, 991

57

56, 58, 113, 115, 170, 172, 227, 229, 284, 286, 341, 343, 398, 400, 455, 457, 512, 514, 569, 571, 626, 628, 683, 685, 740, 742, 797, 799, 854, 856, 911, 913, 968, 970

63

62, 64, 125, 127, 188, 190, 251, 253, 314, 316, 377, 379, 440, 442, 503, 505, 566, 568, 629, 631, 692, 694, 755, 757, 818, 820, 881, 883, 944, 946

65

8, 18, 47, 57, 64, 66, 73, 83, 112, 122, 129, 131, 138, 148, 177, 187, 194, 196, 203, 213, 242, 252, 259, 261, 268, 278, 307, 317, 324, 326, 333, 343, 372, 382, 389, 391, 398, 408, 437, 447, 454, 456, 463, 473, 502, 512, 519, 521, 528, 538, 567, 577, 584, 586, 593, 603, 632, 642, 649, 651, 658, 668, 697, 707, 714, 716, 723, 733, 762, 772, 779, 781, 788, 798, 827, 837, 844, 846, 853, 863, 892, 902, 909, 911, 918, 928, 957, 967, 974, 976, 983, 993

69

68, 70, 137, 139, 206, 208, 275, 277, 344, 346, 413, 415, 482, 484, 551, 553, 620, 622, 689, 691, 758, 760, 827, 829, 896, 898, 965, 967

75

74, 76, 149, 151, 224, 226, 299, 301, 374, 376, 449, 451, 524, 526, 599, 601, 674, 676, 749, 751, 824, 826, 899, 901, 974, 976

77

76, 78, 153, 155, 230, 232, 307, 309, 384, 386, 461, 463, 538, 540, 615, 617, 692, 694, 769, 771, 846, 848, 923, 925, 1000

81

80, 82, 161, 163, 242, 244, 323, 325, 404, 406, 485, 487, 566, 568, 647, 649, 728, 730, 809, 811, 890, 892, 971, 973

85

13, 38, 47, 72, 84, 86, 98, 123, 132, 157, 169, 171, 183, 208, 217, 242, 254, 256, 268, 293, 302, 327, 339, 341, 353, 378, 387, 412, 424, 426, 438, 463, 472, 497, 509, 511, 523, 548, 557, 582, 594, 596, 608, 633, 642, 667, 679, 681, 693, 718, 727, 752, 764, 766, 778, 803, 812, 837, 849, 851, 863, 888, 897, 922, 934, 936, 948, 973, 982

87

86, 88, 173, 175, 260, 262, 347, 349, 434, 436, 521, 523, 608, 610, 695, 697, 782, 784, 869, 871, 956, 958

91

9, 10, 12, 16, 17, 22, 29, 38, 53, 62, 69, 74, 75, 79, 81, 82, 90, 92, 100, 101, 103, 107, 108, 113, 120, 129, 144, 153, 160, 165, 166, 170, 172, 173, 181, 183, 191, 192, 194, 198, 199, 204, 211, 220, 235, 244, 251, 256, 257, 261, 263, 264, 272, 274, 282, 283, 285, 289, 290, 295, 302, 311, 326, 335, 342, 347, 348, 352, 354, 355, 363, 365, 373, 374, 376, 380, 381, 386, 393, 402, 417, 426, 433, 438, 439, 443, 445, 446, 454, 456, 464, 465, 467, 471, 472, 477, 484, 493, 508, 517, 524, 529, 530, 534, 536, 537, 545, 547, 555, 556, 558, 562, 563, 568, 575, 584, 599, 608, 615, 620, 621, 625, 627, 628, 636, 638, 646, 647, 649, 653, 654, 659, 666, 675, 690, 699, 706, 711, 712, 716, 718, 719, 727, 729, 737, 738, 740, 744, 745, 750, 757, 766, 781, 790, 797, 802, 803, 807, 809, 810, 818, 820, 828, 829, 831, 835, 836, 841, 848, 857, 872, 881, 888, 893, 894, 898, 900, 901, 909, 911, 919, 920, 922, 926, 927, 932, 939, 948, 963, 972, 979, 984, 985, 989, 991, 992, 1000

93

92, 94, 185, 187, 278, 280, 371, 373, 464, 466, 557, 559, 650, 652, 743, 745, 836, 838, 929, 931

95

94, 96, 189, 191, 284, 286, 379, 381, 474, 476, 569, 571, 664, 666, 759, 761, 854, 856, 949, 951

99

98, 100, 197, 199, 296, 298, 395, 397, 494, 496, 593, 595, 692, 694, 791, 793, 890, 892, 989, 991

 

Bibliografia

  • Bressoud, David M.;  Factorization and Primality Testing, New York, Springer – Verlag, 1989.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.