Algoritmi sui numeri primi.

Il ritrovo della comunità dove confrontarsi e discutere sulle notizie dal mondo dell'informatica, di Ubuntu e di tutto quello che la riguarda, novità, pettegolezzi e quant'altro.
Avatar utente
Zoff
Moderatore Globale
Moderatore Globale
Messaggi: 33338
Iscrizione: mercoledì 10 ottobre 2007, 22:36

Re: Algoritmi sui numeri primi.

Messaggio da Zoff »

Quel numero non sta in un long long int. Il massimo in un intero a 64bit è 9223372036854775807 ( 18446744073709551615 se unsigned ).

Ti mancano proprio le basi...
Prima di aprire una discussione leggi le Guide, poi vedi se c'è un HowTo nel Wiki e fai una ricerca nel Forum!
Applica semplicemente il [Risolto]! Prova: http://forum.ubuntu-it.org/viewtopic.php?f=70&t=548821
Vuoi qualcosa di piu' dal forum? Prova i miei script: http://forum.ubuntu-it.org/viewtopic.php?f=70&t=597066
P_1_6
Prode Principiante
Messaggi: 20
Iscrizione: giovedì 25 dicembre 2014, 23:01
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggio da P_1_6 »

ho scritto il codice con bigdigits
P_1_6
Prode Principiante
Messaggi: 20
Iscrizione: giovedì 25 dicembre 2014, 23:01
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggio da P_1_6 »

ritengo il primo Test fallito: Troppo tempo.
Avatar utente
DragonLife
Scoppiettante Seguace
Scoppiettante Seguace
Messaggi: 250
Iscrizione: giovedì 28 agosto 2014, 20:03
Desktop: Unity
Distribuzione: Ubuntu 14.04.1 LTS x86_64

Re: Algoritmi sui numeri primi.

Messaggio da DragonLife »

Indipendentemente dal tempo, è riuscito?
Dragonlife
P_1_6
Prode Principiante
Messaggi: 20
Iscrizione: giovedì 25 dicembre 2014, 23:01
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggio da P_1_6 »

l'ho stoppato.
comunque non mi arrendo.
P_1_6
Prode Principiante
Messaggi: 20
Iscrizione: giovedì 25 dicembre 2014, 23:01
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggio da P_1_6 »

mi passate due numeri RSA uno a 30 cifre e uno a 50 cifre che modulo 6 danno 5.
Per vedere se l'algoritmo funziona e posso tentare con quel numero.
Avatar utente
DragonLife
Scoppiettante Seguace
Scoppiettante Seguace
Messaggi: 250
Iscrizione: giovedì 28 agosto 2014, 20:03
Desktop: Unity
Distribuzione: Ubuntu 14.04.1 LTS x86_64

Re: Algoritmi sui numeri primi.

Messaggio da DragonLife »

P_1_6 [url=http://forum.ubuntu-it.org/viewtopic.php?p=4869306#p4869306][img]http://forum.ubuntu-it.org/images/icons/icona-cita.gif[/img][/url] ha scritto:mi passate due numeri RSA uno a 30 cifre e uno a 50 cifre che modulo 6 danno 5.
Per vedere se l'algoritmo funziona e posso tentare con quel numero.
Se provi a fare l'inverso dle tuo programma?
Dragonlife
P_1_6
Prode Principiante
Messaggi: 20
Iscrizione: giovedì 25 dicembre 2014, 23:01
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggio da P_1_6 »

li vorrei da altri se no mi faccio condizionare dal conoscere i primi.
P_1_6
Prode Principiante
Messaggi: 20
Iscrizione: giovedì 25 dicembre 2014, 23:01
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggio da P_1_6 »

Mi è venuta un idea collaborativa dividerci i cicli tra utilizzatori di ubuntu. (da poco l'ho installato ma già mi affascina)
per farlo diventare un progetto Ubuntu come si fa?
Avatar utente
DragonLife
Scoppiettante Seguace
Scoppiettante Seguace
Messaggi: 250
Iscrizione: giovedì 28 agosto 2014, 20:03
Desktop: Unity
Distribuzione: Ubuntu 14.04.1 LTS x86_64

Re: Algoritmi sui numeri primi.

Messaggio da DragonLife »

P_1_6 [url=http://forum.ubuntu-it.org/viewtopic.php?p=4869499#p4869499][img]http://forum.ubuntu-it.org/images/icons/icona-cita.gif[/img][/url] ha scritto:Mi è venuta un idea collaborativa dividerci i cicli tra utilizzatori di ubuntu. (da poco l'ho installato ma già mi affascina)
per farlo diventare un progetto Ubuntu come si fa?
Non saprei ma non hai provato a scrivere in un forum di matematica? Io credo che qui non possiamo darti un grande aiuto...
Dragonlife
P_1_6
Prode Principiante
Messaggi: 20
Iscrizione: giovedì 25 dicembre 2014, 23:01
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggio da P_1_6 »

Si c'ho provato ed ho scritto tante di quelle fesserie in buona fede che ho fatto la fine di "Al lupo, al lupo".
Avatar utente
DragonLife
Scoppiettante Seguace
Scoppiettante Seguace
Messaggi: 250
Iscrizione: giovedì 28 agosto 2014, 20:03
Desktop: Unity
Distribuzione: Ubuntu 14.04.1 LTS x86_64

Re: Algoritmi sui numeri primi.

Messaggio da DragonLife »

P_1_6 [url=http://forum.ubuntu-it.org/viewtopic.php?p=4869652#p4869652][img]http://forum.ubuntu-it.org/images/icons/icona-cita.gif[/img][/url] ha scritto:Si c'ho provato ed ho scritto tante di quelle fesserie in buona fede che ho fatto la fine di "Al lupo, al lupo".
Prova a creare un nuovo account sui loro forum :lol: :birra:
Dragonlife
P_1_6
Prode Principiante
Messaggi: 20
Iscrizione: giovedì 25 dicembre 2014, 23:01
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggio da P_1_6 »

P_1_6 [url=http://forum.ubuntu-it.org/viewtopic.php?p=4869652#p4869652][img]http://forum.ubuntu-it.org/images/icons/icona-cita.gif[/img][/url] ha scritto:Si c'ho provato ed ho scritto tante di quelle fesserie in buona fede che ho fatto la fine di "Al lupo, al lupo".
Questo è uno di quei forum di matematica nei quali ho scritto
P_1_6
Prode Principiante
Messaggi: 20
Iscrizione: giovedì 25 dicembre 2014, 23:01
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggio da P_1_6 »

Avevo pensato questo algoritmo:

EDIT:
vi mostro la strada giusta del 1891
X00-1891=(X-19)09
1891-(X-19)09=(-X+37)82
(X-19)09-(-X+37)82=(2X-57)27
(-X+37)82-(2X-57)27=(-3X+94)55
(2X-57)27-(-3X+94)55=(5X-152)72
(5X-152)72-(-3X+94)55=(8X-246)17
(8X-246)17-(-3X+94)55=(11X-341)62



X00-1891=(X-19)09
1891-(X-19)09=(-X+37)82
X>19 e X<37

Siccome devono essere tutti numeri positivi si ha:
(X-19)09-(-X+37)82=(2X-57)27
X>19 - X<37 = X>28,.... (che è possibile)
invece l'altra strada era
(-X+37)82-(X-19)09=(-2X+57)27
X<37 - X>19 = X<28,.... (che è impossibile)
perchè per ora se il massimo della X è 37 e il minmo è 19 -> 37 - 19 =18 che è minore di 19

(-X+37)82-(2X-57)27=(-3X+94)55
X<37 - X >28,.... = X<31,........ (che è possibile)
invece l'altra strada era
(2X-57)27-(-X+37)82=(3X-94)55
X>28,... - X<37 = X>31,,,,,,, (che è impossibile)
perchè per ora se il massimo della X è 37 e il minmo è 28 -> 37 - 28 =9 che è minore di 31

ecc. ecc.

Quindi ci rimane da stabilire solo
1891-(X-19)09=(-X+37)82
oppure
(X-19)09-1891=(X-37)82

per avere la strada giusta e cioè un Euclide(3100,1891)

Qualcuno vorrebbe scrivere il sorgente per numeri grandi?
vi darò tutte le informazioni

EDIT:
Questa parte in realtà è così
(X-19)09-1891=(X-38)18

-------------------------------------------------
EDIT:
Proviamo a continuare vediamo che succede

1891-(X-38)18=(X+56)73 X<56 (possibile)
e
(X-38)18-1891=(X-57)27 X>57 (impossibile perchè è maggiore della radice quadrata di 1891)

continuiamo
(X-38)18-(X+5673)=-9545 (impossibile perchè è negativo)
e
(X+5673)-(X-38)18=9419
Quindi questo 9419 dovrebbe essere fattorizzabile da 31
quindi facciamo un Euclide(9419,1891) che non da risposte buone
La strada cattiva come vedete viene interrotta.
P_1_6
Prode Principiante
Messaggi: 20
Iscrizione: giovedì 25 dicembre 2014, 23:01
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggio da P_1_6 »

Qualcuno lo ha scritto
Avatar utente
Darren
Scoppiettante Seguace
Scoppiettante Seguace
Messaggi: 402
Iscrizione: giovedì 30 ottobre 2008, 10:08
Desktop: KDE Plasma
Distribuzione: Arch Linux
Sesso: Maschile
Località: Alessandria

Re: Algoritmi sui numeri primi.

Messaggio da Darren »

xchè non ti metti a cercare le master key dei vari Ransomware virus, "potresti" diventare ricco
skype: live:.cid.298cc9477050507b
telegram: @shutter1sland
P_1_6
Prode Principiante
Messaggi: 20
Iscrizione: giovedì 25 dicembre 2014, 23:01
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggio da P_1_6 »

spero un giorno di entrare in un team di ricerca
ma per il momento ho una preparazione da terza media
P_1_6
Prode Principiante
Messaggi: 20
Iscrizione: giovedì 25 dicembre 2014, 23:01
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggio da P_1_6 »

Lo so che ti faccio perdere un sacco di tempo.
Alberico Lepore

Questa è una nuova idea per la fattorizzazione in log:
Allora l'idea è che un numero n=p*q e n ha Cn cifre e p Cp cifre inserite nel algoritmo di Euclide per il calcolo del massimo comun divisore in questo modo
Euclide[ p*(10^(Cn)) , n] ad un certo punto le p cifre davanti scompaiono quindi scompariranno in [log[ 2] ]
Ora è p*100000000-K(45459487)= ad un numero che è minore di di 99999999 (9 Cn volte)
(per un certo K)
quindi le Cp cifre iniziali saranno uguali a zero quindi sarà p-p=0 il secondo p è in chiaro
Alberico Lepore

Ma come lo troviamo K?


Esempio

45459487

X*100000000 - 10030*45459487=X*100000000-455958654610=(X-4560)*100000000+41345390

141345390-45459487=95885903

X*100000000 - 10031*45459487=X*100000000-456004114097=(X-4561)*100000000+95885903

95885903-45459487=50426416

X*100000000 - 10032*45459487=X*100000000-456049573584=(X-4561)*100000000+50426416

50426416-45459487=04966929

X*100000000 - 10033*45459487=X*100000000-456095033971=(X-4561)*100000000+04966929

104966929-45459487=59507442 [DIVERSO1]

X*100000000 - 10034*45459487=X*100000000 -456140492558=(X-4562)*100000000+8675052 [DIVERSO1]

108675052-14047955=94627097 [DIVERSO2]

X*100000000 - 10035*45459487=X*100000000 -456185952045=(X-4562)*100000000+14047955 [DIVERSO2]

Si può ben notare il logaritmo in base 2


Qualcuno vuole implementarlo?

EDIT:

8675052 [DIVERSO1]

Putroppo li c'è un errore di calcolo
P_1_6
Prode Principiante
Messaggi: 20
Iscrizione: giovedì 25 dicembre 2014, 23:01
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggio da P_1_6 »

Ho pensato a questa soluzione però non so risolvere questo sistema

X⋅10000000−Z⋅45459487=3⋅4540513+500000

{(INTERO)[100000000/(Z⋅10+3)]}⋅X=45459487

per (INTERO) intendo parte intera

qualcuno potrebbe darmi una mano
P_1_6
Prode Principiante
Messaggi: 20
Iscrizione: giovedì 25 dicembre 2014, 23:01
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggio da P_1_6 »

Test di primalità e fattorizzazione di Lepore (ultimo)

Eravamo rimasti qui

Definizione
Tutti i numeri NR escluso i multipli di 2 e di 3 si scrivono nella forma 6h+1 e 6h+5.
Dimostrazione
NR modulo 6 =1 -> 6h+1
NR modulo 6 =2 -> è multiplo di 2
NR modulo 6 =3 -> è multiplo di 3
NR modulo 6 =4 -> è multiplo di 2
NR modulo 6 =5 -> 6h+1
NR modulo 6 =0 -> è multiplo di 2 e di 3

Lemma
Quindi partendo da 1 e facendo +2 e +4 si ha
1 5 7 11 13 17 19 23 25 29 ecc.ecc.

Definizione
Ogni numero NR escluso i multipli di 2 e di 3 si scrivono nella forma
1) X^2+6nX=NR
2) X^2+6nX+2X=NR
3) X^2+6nX+4X=NR
Dimostrazione
Dal lemma segue direttamente
1) X(X+6n)=NR
2) X(X+6n+2)=NR
3) X(X+6n+4)=NR

In più si può osservare che:
(6h+1)*(6k+1)=6G+1
(6h+5)*(6k+5)=6G+1
(6h+1)*(6k+5)=6G+5
(6h+5)*(6k+1)=6G+5
----------------------------------------------------------------------------------------
Da ciò si può dedurre che risolvendo (6h+1)*(6k+1)=6G+1
si possano risolvere gli altri tre casi
questi
(6h+1)*(6k+5)=6G+5
(6h+5)*(6k+1)=6G+5
moltiplicando per 5
e questo
(6h+5)*(6k+5)=6G+1
moltiplicando per 25
utilizzo questo per non scrivere quattro algoritmi diversi ma uno solo
----------------------------------------------------------------------------------
Per capire il ragionamento ci scriviamo in una tabella tutti gli NR generati da
X^2+6nX=NR
con x che parte da 1 e fa +6
cioè 1 7 13 19 35 31 37 43 ecc. ecc
e con n che parte da 1 e fa +1
cioè 1 2 3 4 5 6 ecc. ecc.

Ho scoperto delle nuove cose:
(a) questa tabella è divisa in atomi
(b) funziona come lo snake (il gioco) [c'è un eccezione che si capisce dall'algoritmo]
(c) se trovi la diagonale hai trovato il tesoro

(a) ogni numero di questa tabella è circondato da numeri e questa circonferenza compreso il numero stesso è ordinata
esempio 1333
è ordinato così 775 925 1075 1147 1333 1519 1591 1813 2035
esempio 91
è ordinato così 91 133 247 325

(b) ogni numero N di questa tabella è raggiungibile da un qualsiasi altro numero di questa tabella
si sceglie un numero e si guarda tutto l'atomo il valore più vicino al numero da cercare N sarà il fulcro del prossimo atomo fino ad arrivare al numero stesso N
esempio N=1333 e partiamo da ad esempio 91
la sequenza di fulcri sarà 91 325 703 1225 1075 1333
esempio 1375 e partiamo ad esempio da 775
la sequenza sarà 775 1333 1519 1225 1375

(c) ogni numero di questa tabella è identificato dalle regole di (b) con una diagonale
esempio 1891
la diagonale sarà 91 325 703 1225 1891
esempio 2035
la diagonale sarà 775 133 2035
esempio 1375
la diagonale sarà 133 403 817 1375

Algoritmo

Sia N=p*q con p , q ed N nella forma 6*h+1
Si troverà la fattorizzazione in al massimo logaritmo di [(N - F)/6] dove F è il primo numero dopo la radice quadrata di N nella forma 6*h+1.
Le regole del logaritmo:

scelto un G nell'intervallo [(N - F)/6] allora g=6*G+1
Testo se N modulo g = 0
Testo se N modulo {6*{parte inferiore di [(N/g)/6]}+7}=0
Testo se N modulo {6*{parte superiore di [(N/g)/6]}+7}=0

se g*7 > N allora G deve scendere
altrimenti
se g*(g-6) < N allora G deve salire
altrimenti

se{N-{6*{parte inferiore di [(N/g)/6]}+1}}*g < {N-{6*{parte superiore di [(N/g)/6]}+1}*g}
se {N-{6*{parte inferiore di [(N/g)/6]}+1}}*(g-6) < {N-{6*{parte inferiore di [(N/g)/6]}+1}*(g+6)}
allora G deve scendere
altrimenti
se {N-{6*{parte inferiore di [(N/g)/6]}+1}}*(g-6) > {N-{6*{parte inferiore di [(N/g)/6]}+1}*(g+6)}
allora G deve salire
altrimenti

se{N-{6*{parte inferiore di [(N/g)/6]}+1}}*g > {N-{6*{parte superiore di [(N/g)/6]}+1}*g}
se {N-{6*{parte superiore di [(N/g)/6]}+1}}*(g-6) < {N-{6*{parte superiore di [(N/g)/6]}+1}*(g+6)}
allora G deve scendere
altrimenti
se {N-{6*{parte superiore di [(N/g)/6]}+1}}*(g-6) > {N-{6*{parte superiore di [(N/g)/6]}+1}*(g+6)}
allora G deve salire

Speranzoso di non aver commesso errori e in un vostro riscontro cordialmente vi saluto
Alberico Lepore
Scrivi risposta

Ritorna a “Bar Ubuntu”

Chi c’è in linea

Visualizzano questa sezione: caturen, tom tom e 19 ospiti