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

Primi di Solinas

Teoria dei numeri 

Si chiamano “primi di Solinas” i numeri primi della forma 2m ± 2n ± 1 con m > n > 0.

Prendono il nome da Jerome Solinas, che nel 1999 dimostrò che che le divisioni per primi di Solinas e il calcolo dei relativi resti possono essere ridotti a una sequenza di addizioni e sottrazioni, molto veloci da calcolare, anche per numeri enormi.

I primi di Solinas trovano quindi impiego negli algoritmi crittografici, laddove sono richiesti calcoli modulo un numero primo.

 

I primi di Solinas minori di 106 sono:

3 = 22 – 2 + 1 = 23 – 22 – 1;

5 = 22 + 2 – 1 = 23 – 2 – 1 = 23 – 22 + 1;

7 = 22 + 2 + 1 = 23 – 2 + 1 = 24 – 23 – 1;

11 = 23 + 2 + 1 = 23 + 22 – 1 = 24 – 22 – 1;

13 = 23 + 22 + 1 = 24 – 2 – 1 = 24 – 22 + 1;

17 = 24 + 2 – 1 = 25 – 24 + 1;

19 = 24 + 2 + 1 = 24 + 22 – 1;

23 = 24 + 23 – 1 = 25 – 23 – 1;

29 = 25 – 2 – 1 = 25 – 22 + 1;

31 = 25 – 2 + 1 = 26 – 25 – 1;

37 = 25 + 22 + 1;

41 = 25 + 23 + 1;

47 = 25 + 24 – 1 = 26 – 24 – 1;

59 = 26 – 22 – 1;

61 = 26 – 2 – 1 = 26 – 22 + 1;

67 = 26 + 2 + 1 = 26 + 22 – 1;

71 = 26 + 23 – 1;

73 = 26 + 23 + 1;

79 = 26 + 24 – 1;

97 = 26 + 25 + 1 = 27 – 25 + 1;

113 = 27 – 24 + 1;

127 = 27 – 2 + 1 = 28 – 27 – 1;

131 = 27 + 21 + 1 = 27 + 22 – 1;

137 = 27 + 23 + 1;

191 = 27 + 26 – 1 = 28 – 26 – 1;

193 = 27 + 26 + 1 = 28 – 26 + 1;

223 = 28 – 25 – 1;

239 = 28 – 24 – 1;

241 = 28 – 24 + 1;

251 = 28 – 22 – 1;

257 = 28 + 2 – 1 = 29 – 28 + 1;

263 = 28 + 23 – 1;

271 = 28 + 24 – 1;

383 = 28 + 27 – 1 = 29 – 27 – 1;

449 = 29 – 26 + 1;

479 = 29 – 25 – 1;

503 = 29 – 23 – 1;

509 = 29 – 21 – 1 = 29 – 22 + 1;

521 = 29 + 23 + 1;

577 = 29 + 26 + 1;

641 = 29 + 27 + 1;

769 = 210 – 28 + 1;

769 = 29 + 28 + 1;

991 = 210 – 25 – 1;

1009 = 210 – 24 + 1 = 210 – 22 – 1;

1021 = 210 – 2 – 1 = 210 – 22 + 1;

1031 = 210 + 23 – 1:

1033 = 210 + 23 + 1;

1039 = 210 + 24 – 1;

1087 = 210 + 26 – 1;

1151 = 210 + 27 – 1;

1153 = 210 + 27 + 1;

1279 = 210 + 28 – 1;

2017 = 211 – 25 + 1;

2039 = 211 – 23 – 1;

2053 = 211 + 22 + 1;

2063 = 211 + 24 – 1;

2081 = 211 + 25 + 1;

2111 = 211 + 26 – 1;

2113 = 211 + 26 + 1;

3583 = 212 – 29 – 1;

3967 = 212 – 27 – 1;

4079 = 212 – 24 – 1;

4091 = 212 – 22 – 1;

4093 = 212 – 21 – 1 = 212 – 22 + 1;

4099 = 212 + 21 + 1 = 212 + 22 – 1;

4111 = 212 + 24 – 1;

4127 = 212 + 25 – 1;

4129 = 212 + 25 + 1;

4159 = 212 + 26 – 1;

5119 = 212 + 210 – 1;

6143 = 212 + 211 – 1 = 213 – 211 – 1;

7681 = 213 – 29 + 1;

7937 = 213 – 28 + 1;

8161 = 213 – 25 + 1;

8191 = 213 – 2 + 1 = 214 – 213 – 1;

8209 = 213 + 24 + 1;

8447 = 213 + 28 – 1;

12289 = 213 + 212 + 1 = 214 – 212 + 1;

15359 = 214 – 210 – 1;

15361 = 214 – 210 + 1;

16127 = 214 – 28 – 1;

16319 = 214 – 26 – 1;

16369 = 214 – 24 + 1;

16381 = 214 – 2 – 1 = 214 – 22 + 1;

16417 = 214 + 25 + 1;

16447 = 214 + 26 – 1;

18433 = 214 + 211 + 1;

20479 = 214 + 212 – 1;

32257 = 215 – 29 + 1;

32771 = 215 + 2 + 1 = 215 + 22 – 1;

32783 = 215 + 24 – 1;

32801 = 215 + 25 + 1;

32831 = 215 + 26 – 1;

32833 = 215 + 26 + 1;

33023 = 215 + 28 – 1;

33791 = 215 + 210 – 1;

40961 = 215 + 213 + 1;

61441 = 216 – 212 + 1;

63487 = 216 – 211 – 1;

64513 = 216 – 210 + 1;

65407 = 216 – 27 – 1;

65519 = 216 – 24 – 1;

65521 = 216 – 24 + 1;

65537 = 216 + 2 – 1 = 217 – 216 + 1;

65539 = 216 + 2 + 1 = 216 + 22 – 1;

65543 = 216 + 23 – 1;

65551 = 216 + 24 – 1;

65599 = 216 + 26 – 1;

66047 = 216 + 29 – 1;

73727 = 216 + 213 – 1;

81919 = 216 + 214 – 1;

114689 = 217 – 214 + 1;

129023 = 217 – 211 – 1;

130817 = 217 – 28 + 1;

131009 = 217 – 26 + 1;

131041 = 217 – 25 + 1;

131063 = 217 – 23 – 1;

131071 = 217 – 2 + 1 = 218 – 217 – 1;

133121 = 217 + 211 + 1;

147457 = 217 + 214 + 1;

163841 = 217 + 215 + 1;

245759 = 218 – 214 – 1;

253951 = 218 – 213 – 1;

261631 = 218 – 29 – 1;

261887 = 218 – 28 – 1;

262079 = 218 – 26 – 1;

262111 = 218 – 25 – 1;

262127 = 218 – 24 – 1;

262139 = 218 – 22 – 1;

262147 = 218 + 2 + 1 = 218 + 22 – 1;

262151 = 218 + 23 – 1;

262153 = 218 + 23 + 1;

262271 = 218 + 27 – 1;

262399 = 218 + 28 – 1;

262657 = 218 + 29 + 1;

263167 = 218 + 210 – 1;

266239 = 218 + 212 – 1;

270337 = 218 + 213 + 1;

294911 = 218 + 215 – 1;

520193 = 219 – 212 + 1;

522239 = 219 – 211 – 1;

523777 = 219 – 29 + 1;

524257 = 219 – 25 + 1;

524287 = 219 – 2 + 1 = 220 – 219 – 1;

524351 = 219 + 26 – 1;

524353 = 219 + 26 + 1;

524801 = 219 + 29 + 1;

525313 = 219 + 210 + 1;

528383 = 219 + 212 – 1;

557057 = 219 + 215 + 1;

786431 = 219 + 218 – 1 = 220 – 218 – 1;

786433 = 219 + 218 + 1 = 220 – 218 + 1;

917503 = 220 – 217 – 1.

 

I primi di Solinas sono relativamente rari in assoluto, ma frequenti tra i primi piccoli: il minimo primo dispari non di Solinas è 43.

 

Sono primi di Solinas in due modi diversi:

  • i primi di Fermat, perché 22n + 1 = 22n + 2 – 1 = 22n + 1 – 22n + 1;

  • i primi di Mersenne, perché 2n – 1 = 2n – 2 + 1 = 2n + 1 – 2n – 1;

  • i primi della forma 2n – 3, perché 2n – 3 = 2n – 22 + 1 = 2n – 2 – 1;

  • i primi della forma 2n + 3, perché 2n + 3 = 2n + 22 – 1 = 2n + 2 + 1;

  • i primi della forma 3 · 2n ± 1, perché 3 · 2n ± 1 = 2n + 1 + 2n ± 1 = 2n + 2 – 2n ± 1.

 

Gli unici numeri che sono primi di Solinas in tre modi diversi sono:

5 = 22 + 2 – 1 = 23 – 2 – 1 = 23 – 22 + 1;

7 = 22 + 2 + 1 = 23 – 2 + 1 = 24 – 23 – 1;

11 = 23 + 2 + 1 = 23 + 22 – 1 = 24 – 22 – 1;

13 = 23 + 22 + 1 = 24 – 2 – 1 = 24 – 22 + 1.

Vedi anche

Primi (numeri).

Contattami

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