C++ - Ricerca numeri primi

Pubblicità
Non ho mai parlato di malfunzionamento, ma se ad una proprietà (quella che i semiprimi, ottenuti dalla moltiplicazione di due generici primi appartenenti a due determinati intervalli, siano tutti divisibili per un determinato valore da te chiamato chiave) matematicamente non dimostrata aggiungi il fatto che i primi sono ottenuti con un metodo su base probabilistica, non mi sembra che il termine "aleatorio" sia così campato in aria.
E comunque non c'è bisogno di prendersela, lo sai che mi sto impegnando nel cercare di venire matematicamente a capo del problema. Infatti l'argomento di questo topic nasce proprio dal fatto di voler testare il tuo algoritmo, ma non conoscendo il python sto cercando di implementare una funzione next_prime_number() in C++, da associare poi alla libreria sui big_int che ho scritto qualche tempo fa.
Clicca per espandere...

Non me la prendo, perchè dovrei? La tua risposta comunque la prendo come un si.
 
M1n021 ha detto:
Non ho mai parlato di malfunzionamento, ma se ad una proprietà (quella che i semiprimi, ottenuti dalla moltiplicazione di due generici primi appartenenti a due determinati intervalli, siano tutti divisibili per un determinato valore da te chiamato chiave) matematicamente non dimostrata aggiungi il fatto che i primi sono ottenuti con un metodo su base probabilistica, non mi sembra che il termine "aleatorio" sia così campato in aria.
E comunque non c'è bisogno di prendersela, lo sai che mi sto impegnando nel cercare di venire matematicamente a capo del problema. Infatti l'argomento di questo topic nasce proprio dal fatto di voler testare il tuo algoritmo, ma non conoscendo il python sto cercando di implementare una funzione next_prime_number() in C++, da associare poi alla libreria sui big_int che ho scritto qualche tempo fa.
Clicca per espandere...

Non si se hai spulciato anche il sorgente per vedere nextprime: https://github.com/sympy/sympy/blob/sympy-1.13.2/sympy/ntheory/generate.py#L629

Il crivello usato è quello di Eratostene, guardando sieve() (espanso dinamicamente, come fai tu).
 
DispatchCode ha detto:
Non si se hai spulciato anche il sorgente per vedere nextprime: https://github.com/sympy/sympy/blob/sympy-1.13.2/sympy/ntheory/generate.py#L629

Il crivello usato è quello di Eratostene, guardando sieve() (espanso dinamicamente, come fai tu).
Clicca per espandere...
No, ma cercando su google avevo letto che utilizza un algoritmo su base probabilistica per valori maggiori di 2^64-1. Forse utilizza il crivello per numeri più piccoli e il metodo probabilistico per quelli più grandi. Per caso sei riuscito a capire anche quale algoritmo probabilistico utilizza?
 
M1n021 ha detto:
No, ma cercando su google avevo letto che utilizza un algoritmo su base probabilistica per valori maggiori di 2^64-1. Forse utilizza il crivello per numeri più piccoli e il metodo probabilistico per quelli più grandi. Per caso sei riuscito a capire anche quale algoritmo probabilistico utilizza?
Clicca per espandere...

Avevo letto anche io, ma guardando il codice la cosa non mi torna molto (cioè, non mi sembra di vedere controlli di quel tipo, ma non ho verificato isprime () che check per esempio). Però l'ho guardato da smartphone, da PC provo a dare un'altra occhiata.

EDIT:

"Finally if the number is larger than 2^64, a strong
BPSW test is performed. While this is a probable prime test and we
believe counterexamples exist, there are no known counterexamples"

È proprio nel check di isprime().
Ora leggo il codice

github.com

sympy/sympy/ntheory/primetest.py at sympy-1.13.2 · sympy/sympy

A computer algebra system written in pure Python. Contribute to sympy/sympy development by creating an account on GitHub.
github.com github.com
 

Test Deterministici​

1. Divisione per Tentativi​

  • Caratteristiche: Semplice ma inefficiente per numeri grandi.
  • Uso: Numeri piccoli, situazioni didattiche.
  • Perché: Facile da implementare e comprendere.

2. Crivello di Eratostene​

  • Caratteristiche: Efficiente per trovare tutti i primi fino a un certo limite.
  • Uso: Generazione di tavole di numeri primi, applicazioni matematiche.
  • Perché: Ottimo per pre-calcolare set di numeri primi.

3. Test AKS (Agrawal-Kayal-Saxena)​

  • Caratteristiche: Primo test deterministico in tempo polinomiale.
  • Uso: Principalmente di interesse teorico.
  • Perché: Prova la primalità in tempo polinomiale, ma spesso troppo lento per usi pratici.

4. Test di Lucas-Lehmer​

  • Caratteristiche: Specifico per numeri di Mersenne.
  • Uso: Ricerca di grandi numeri primi di Mersenne.
  • Perché: Estremamente efficiente per questa classe specifica di numeri.

5. Test Deterministico di Miller​

  • Caratteristiche: Versione deterministica del test di Miller-Rabin.
  • Uso: Prova rigorosa di primalità.
  • Perché: Garantisce la correttezza, ma richiede la conoscenza dell'ipotesi di Riemann estesa.

Test Probabilistici​

6. Test di Fermat​

  • Caratteristiche: Rapido ma può fallire con i numeri di Carmichael.
  • Uso: Come pre-test rapido prima di test più rigorosi.
  • Perché: Veloce e semplice da implementare.

7. Test di Miller-Rabin​

  • Caratteristiche: Molto affidabile e efficiente.
  • Uso: Ampiamente utilizzato in crittografia e software matematico.
  • Perché: Offre un buon equilibrio tra velocità e affidabilità.

8. Test di Solovay-Strassen​

  • Caratteristiche: Basato sul simbolo di Jacobi.
  • Uso: Meno comune del Miller-Rabin, ma ancora utilizzato in alcuni contesti.
  • Perché: Storicamente importante, ancora utile in alcune applicazioni specifiche.

9. Test di Baillie-PSW​

  • Caratteristiche: Combina Miller-Rabin e un test di Lucas probabilistico.
  • Uso: Verifica di primalità in software matematici.
  • Perché: Molto affidabile, nessun falso positivo noto.

10. Test di Frobenius​

  • Caratteristiche: Basato sulle proprietà dell'anello degli interi modulo n.
  • Uso: Alternative al Miller-Rabin in alcuni contesti.
  • Perché: Può essere più veloce per alcuni numeri specifici.

Test Ibridi e Avanzati​

11. ECPP (Elliptic Curve Primality Proving)​

  • Caratteristiche: Utilizza curve ellittiche per provare la primalità.
  • Uso: Prova rigorosa per numeri molto grandi.
  • Perché: Può fornire certificati di primalità per numeri estremamente grandi.

12. APR-CL (Adleman-Pomerance-Rumely, Cohen-Lenstra)​

  • Caratteristiche: Test ciclotomico.
  • Uso: Prova rigorosa per numeri di dimensioni moderate.
  • Perché: Più veloce dell'ECPP per alcuni intervalli di numeri.

13. Test di Proth​

  • Caratteristiche: Specifico per numeri della forma k·2^n + 1.
  • Uso: Ricerca di numeri primi di Proth.
  • Perché: Efficiente per questa forma specifica di numeri.
 
Ultima modifica da un moderatore:
M1n021 ha detto:
Eh sì, essendo l'algoritmo probabilistico in fin dei conti un test di primalità, è giusto che sia lì.


Non conosco il python, ma dai riferimenti riportati mi sembra di capire che il test utilizzato sia il seguente:

Baillie–PSW primality test - Wikipedia

en.wikipedia.org en.wikipedia.org
Clicca per espandere...
Davo per scontato fosse lì, non poteva che essere così considerando che il risultato effettivo lo restituisce quella funzione e ogni blocco del codice ne fa uso.

Si, comunque è quello sicuramente usato.

piergiac-1 ha detto:

Test Deterministici​


1. Divisione per Tentativi​


  • Caratteristiche: Semplice ma inefficiente per numeri grandi.
  • Uso: Numeri piccoli, situazioni didattiche.
  • Perché: Facile da implementare e comprendere.

2. Crivello di Eratostene​


  • Caratteristiche: Efficiente per trovare tutti i primi fino a un certo limite.
  • Uso: Generazione di tavole di numeri primi, applicazioni matematiche.
  • Perché: Ottimo per pre-calcolare set di numeri primi.

3. Test AKS (Agrawal-Kayal-Saxena)​


  • Caratteristiche: Primo test deterministico in tempo polinomiale.
  • Uso: Principalmente di interesse teorico.
  • Perché: Prova la primalità in tempo polinomiale, ma spesso troppo lento per usi pratici.

4. Test di Lucas-Lehmer​


  • Caratteristiche: Specifico per numeri di Mersenne.
  • Uso: Ricerca di grandi numeri primi di Mersenne.
  • Perché: Estremamente efficiente per questa classe specifica di numeri.

5. Test Deterministico di Miller​


  • Caratteristiche: Versione deterministica del test di Miller-Rabin.
  • Uso: Prova rigorosa di primalità.
  • Perché: Garantisce la correttezza, ma richiede la conoscenza dell'ipotesi di Riemann estesa.

Test Probabilistici​


6. Test di Fermat​


  • Caratteristiche: Rapido ma può fallire con i numeri di Carmichael.
  • Uso: Come pre-test rapido prima di test più rigorosi.
  • Perché: Veloce e semplice da implementare.

7. Test di Miller-Rabin​


  • Caratteristiche: Molto affidabile e efficiente.
  • Uso: Ampiamente utilizzato in crittografia e software matematico.
  • Perché: Offre un buon equilibrio tra velocità e affidabilità.

8. Test di Solovay-Strassen​


  • Caratteristiche: Basato sul simbolo di Jacobi.
  • Uso: Meno comune del Miller-Rabin, ma ancora utilizzato in alcuni contesti.
  • Perché: Storicamente importante, ancora utile in alcune applicazioni specifiche.

9. Test di Baillie-PSW​


  • Caratteristiche: Combina Miller-Rabin e un test di Lucas probabilistico.
  • Uso: Verifica di primalità in software matematici.
  • Perché: Molto affidabile, nessun falso positivo noto.

10. Test di Frobenius​


  • Caratteristiche: Basato sulle proprietà dell'anello degli interi modulo n.
  • Uso: Alternative al Miller-Rabin in alcuni contesti.
  • Perché: Può essere più veloce per alcuni numeri specifici.

Test Ibridi e Avanzati​


11. ECPP (Elliptic Curve Primality Proving)​


  • Caratteristiche: Utilizza curve ellittiche per provare la primalità.
  • Uso: Prova rigorosa per numeri molto grandi.
  • Perché: Può fornire certificati di primalità per numeri estremamente grandi.

12. APR-CL (Adleman-Pomerance-Rumely, Cohen-Lenstra)​


  • Caratteristiche: Test ciclotomico.
  • Uso: Prova rigorosa per numeri di dimensioni moderate.
  • Perché: Più veloce dell'ECPP per alcuni intervalli di numeri.

13. Test di Proth​


  • Caratteristiche: Specifico per numeri della forma k·2^n + 1.
  • Uso: Ricerca di numeri primi di Proth.
  • Perché: Efficiente per questa forma specifica di numeri.
Clicca per espandere...
Grazie per averci incollato la risposta di GPT...
 
DispatchCode ha detto:
Non si se hai spulciato anche il sorgente per vedere nextprime: https://github.com/sympy/sympy/blob/sympy-1.13.2/sympy/ntheory/generate.py#L629

Il crivello usato è quello di Eratostene, guardando sieve() (espanso dinamicamente, come fai tu).
Clicca per espandere...
Per curiosità sono andato a vedere l'implementazione del crivello, anche per fare un paragone con la mia, ma sinceramente ad un lettura veloce, considerando anche il fatto che non conosco il python, non ci ho capito più di tanto! 😅
Più che altro mi interessava capire come affrontava questa specifica questione:
M1n021 ha detto:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103
107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 205
207 209 211 213 215 217 219 221 223 225 227 229 231 233 235 237 239 241 243 245
247 249 251 253 255 257 259 261 263 265 267 269 271 273 275 277 279 281 283 285
287 289 291 293 295 297 299 301 303 305 307 309 311 313 315 317 319 321 323 325
327 329 331 333 335 337 339 341 343 345 347 349 351 353 355 357 359 361 363 365
367 369 371 373 375 377 379 381 383 385 387 389 391 393 395 397 399 401 403

I numeri da "crivellare" sono quelli in nero, e chiamiamo m l'indice del primo di questa sequenza (ossia di 205).
Nel classico algoritmo del crivello di Eratostene quando si vogliono eliminare i multipli di 17 si parte ovviamente dal suo quadrato ossia 17*17=289, e in questo caso, essendo 289>205, sarà lo stesso anche qui, e quindi non resta che ricavare l'indice associato a 289, che può essere calcolato come m+(289-205)/2.
Nel momento in cui invece vogliamo eliminare i multipli di 7 le cose cambiano, essendo 49<205; in questo caso dobbiamo trovare il primo multiplo dispari di 7 che sia >=205 e ricavare poi il suo indice nell'array. Ed è qui che entra in gioco:

k = r ? (r % 2 ? (n - r) / 2 : n - r / 2) : 0;

In pratica mi sono reso conto che il resto di numeri dispari successivi per un determinato numero dispari a genera una sequenza ciclica costituita prima dai numeri pari e poi dai numeri dispari minori di a . Per esempio nel caso di a=7 avremo

0 2 4 6 1 3 5 0 ...

mentre per a=19 avremo

0 2 4 6 8 10 12 14 16 18 1 3 5 7 9 11 13 15 17 0 ...

E la formula "illeggibile" di cui sopra, non fa altro che sfruttare questa proprietà.
Clicca per espandere...
 
Pubblicità
Pubblicità
Indietro
Top