In rete: http://www.elegio.it/max/algoritmo-euclide-esteso.html

Provo le funzioni di questo documento:

...

...

Per curiosità, scrivendo con Maxima zn_primroot(1000000000039) si ottiene 3 ossia 3 è la più piccola radice primitiva di 1000000000039.

Algoritmo di Euclide esteso, programmato in Javascript

Calcola d, v e w assegnando a e e b.

a = ; b = :

.?.

In pratica è questo ( apparentemente semplice ) algoritmo:

function esteso_mcd(a,b){ var d=Math.round(a),t=Math.round(b),q, x=0,y=1,z=0,v=1,w=0; while(t!=0){ z=d%t; q=(d-z)/t; d=t; t=z; z=x; x=v-q*x; v=z; z=y; y=w-q*y; w=z; } return [d,v,w]; }

Come risultato il primo termine ossia d è il massimo comun divisore ( in maximese ossia nel linguaggio di http://maxima.sourceforge.net/ si ottiene scrivendo  gcd(a,b)  ) mentre gli altri due termini, v e w, sono i fattori che servono per fare la combinazione lineare tra i due argomenti in modo che dia come risultato appunto il massimo comun divisore ossia  a*v+b*w=d .

Supponiamo che b sia un numero primo ( ad esempio qualche primo che serve per creare primi di Mersenne, ossia 57885161 oppure 43112609 oppure 37156667 oppure 32582657 oppure 30402457 oppure 25964951 oppure 24036583 oppure 20996011 oppure 13466917 oppure 6972593 ... usabili per ottenere, per esempio  2^57885161 −1  enorme primo di Mersenne ). Allora ogni a < p ha, come massimo comun divisore, 1. Se calcoliamo il modulo di questa espressione rispetto a b abbiamo che ovviamente  (b*w)%b  in Javascript o  mod(b*w,b)  in maximese vale zero e dunque (a*v)%b=1 il che vuol dire che v rappresenta l'intero inverso di a quando si lavora modulo b.

Cercare con Maxima primi enormi QUASI potenze di 10

E' un modo per giocare con grandi numeri primi e per mettere a dura prova Maxima...

Con Maxima ho trovano che sono primi:

10¹ −3 ossia 7, con radice primitiva 3

10² −3 ossia 97, con radice primitiva 5

10³ −3 ossia 997, con radice primitiva 7

10¹⁷ −3 ossia 99999999999999997, con radice primitiva 2

Da qui in poi Maxima non riesce a trovare una radice primitiva...

10¹⁴⁰ −3 ma radice primitiva ignota.

10⁹⁹⁰ −3 ma radice primitiva ignota.

10¹⁸⁸⁷ −3 ma radice primitiva ignota.

Insomma ... forse l'ultimo andrebbe conservato come enorme primo... o no ?

Qualcosa di analogo si può fare sottraendo 9 e non 3 alla potenza di 10.

10³ −9 con radice primitiva 6

10⁵ −9 con radice primitiva 6

10⁷ −9 con radice primitiva 22

10³³ −9 con radice primitiva 6

10⁴⁵ −9 con radice primitiva 7

Da qui in poi Maxima non riesce a trovare una radice primitiva...

10¹⁰⁵ −9 ma con radice primitiva ignota

10¹⁹⁷ −9 ma con radice primitiva ignota

10¹⁹⁹ −9 ma con radice primitiva ignota

10²⁸¹ −9 ma con radice primitiva ignota

10³⁰¹ −9 ma con radice primitiva ignota

10³¹⁷ −9 ma con radice primitiva ignota

10¹¹⁰⁷ −9 ma con radice primitiva ignota

10¹⁶⁵⁷ −9 ma con radice primitiva ignota

Il file che ho usato per fare questi calcoli, salvato con l'estensione .mac è di puro testo e lo ricopio qua di seguito:

timedate(absolute_real_time()-8*3600);

/*
Cerco i primi esprimibili nella forma 10^j-3 ossia QUASI una
potenza di 10 esatta.
Per questo tipo di primi è relativamente poco costoso calcolare
il modulo...
*/

for j:1 step 1 thru 100 do(
primo:10^j-3,
if primep(primo) then (
proot:primitivaradice:zn_primroot(primo),
disp(concat(j,"] Primo con radice primitiva ",proot),primo)
));

/*
Dunque è primo 7, 97, 997 e 10^17-3 ma da qui in poi i primi
esprimibili nella forma 10^k-3 sono rarissimi !
*/

/*
Dunque le radici primitive più piccole di 7,97,997 e 99999999999999997
sono rispettivamente 3,5,7,2.
*/

/*
Ora esamino i primi nella forma 10^j-9
*/

for j:1 step 1 thru 50 do(
primo:10^j-9,
if primep(primo) then (
proot:primitivaradice:zn_primroot(primo),
disp(concat(j,"] Primo con radice primitiva ",proot),primo)
));

/*
Dunque :
10^3-9 ha radice primitiva 6,
10^5-9 ha radice primitiva 6
10^7-9 ha radice primitiva 22
10^33-9 ha radice primitiva 6
10^45-9 ha radice primitiva 7
Ora esploro primi più grossi ma ... quasi ingestibili..
*/

for j:1650 step 1 thru 1660 do(
primo:10^j-9,
if primep(primo) then (
disp(concat(j,"] Primo "),primo)
));

/*
Dunque sono primi ma di radice primitiva sconosciuta ( calcolo 
di lunghissima durata )
10^105-9 
10^197-9
10^199-9
10^281-9
10^301-9
10^317-9
10^1107-9
10^1657-9
*/

/*
Ora faccio una ricerca pesante, fino all'esponente 1000 di
primi della forma 10^j-3 ossia più prossimi alla 
esatta potenza di 10...
*/

for j:100 step 1 thru 1000 do(
primo:10^j-3,
if primep(primo) then disp(concat(j,") Primo"),primo));

/*
Dunque è primo 10^140-3 e 10^990-3 ed ovviamente Maxima ci mette 
un bel po' a trovare 10^990-3 !
*/

/*
Ho fatto eseguire per qualche ora l'espressione:
zn_primroot(10^140-3);
MA NON HA SAPUTO TROVARE LA RADICE PRIMITIVA DI QUESTO PRIMO...
Ora vado avanti in questa lunghissima ricerca fino
all'esponente 2000.
*/

for j:980 step 1 thru 2000 do(
primo:10^j-3,
if mod(j,97)=0 then disp(concat("Passo ",j)),
if primep(primo) then disp(concat(j,") Primo"),primo));

/*
Da questi calcoli emerge che è primo anche 10^1887-3
*/

Bibliografia

• http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
• http://it.wikipedia.org/wiki/Teorema_cinese_del_resto
• http://en.wikipedia.org/wiki/Pythagorean_triple
• http://www.elegio.it/doc/tn/ mie pagine dedicate alla teoria dei numeri ed alla crittografia.

Giampaolo Bottoni gpbottoni@gmail.com http://www.alumni.polimi.it/it/Wall ( ing. nucleare 1972 )