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.

Re: Algoritmi sui numeri primi.

Messaggioda Zoff » martedì 5 aprile 2016, 10:27

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: viewtopic.php?f=70&t=548821
Vuoi qualcosa di piu' dal forum? Prova i miei script: viewtopic.php?f=70&t=597066
Avatar utente
Zoff
Moderatore Globale
Moderatore Globale
 
Messaggi: 33316
Iscrizione: ottobre 2007

Re: Algoritmi sui numeri primi.

Messaggioda P_1_6 » martedì 5 aprile 2016, 10:38

ho scritto il codice con bigdigits
P_1_6
Prode Principiante
 
Messaggi: 19
Iscrizione: dicembre 2014
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggioda P_1_6 » martedì 5 aprile 2016, 12:16

ritengo il primo Test fallito: Troppo tempo.
P_1_6
Prode Principiante
 
Messaggi: 19
Iscrizione: dicembre 2014
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggioda DragonLife » martedì 5 aprile 2016, 17:14

P_1_6 Immagine ha scritto:ritengo il primo Test fallito: Troppo tempo.

Indipendentemente dal tempo, è riuscito?
Dragonlife
Avatar utente
DragonLife
Scoppiettante Seguace
Scoppiettante Seguace
 
Messaggi: 250
Iscrizione: agosto 2014
Desktop: Unity
Distribuzione: Ubuntu 14.04.1 LTS x86_64

Re: Algoritmi sui numeri primi.

Messaggioda P_1_6 » martedì 5 aprile 2016, 17:31

l'ho stoppato.
comunque non mi arrendo.
P_1_6
Prode Principiante
 
Messaggi: 19
Iscrizione: dicembre 2014
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggioda P_1_6 » martedì 5 aprile 2016, 17:53

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.
P_1_6
Prode Principiante
 
Messaggi: 19
Iscrizione: dicembre 2014
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggioda DragonLife » martedì 5 aprile 2016, 17:58

P_1_6 Immagine 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
Avatar utente
DragonLife
Scoppiettante Seguace
Scoppiettante Seguace
 
Messaggi: 250
Iscrizione: agosto 2014
Desktop: Unity
Distribuzione: Ubuntu 14.04.1 LTS x86_64

Re: Algoritmi sui numeri primi.

Messaggioda P_1_6 » martedì 5 aprile 2016, 18:02

li vorrei da altri se no mi faccio condizionare dal conoscere i primi.
P_1_6
Prode Principiante
 
Messaggi: 19
Iscrizione: dicembre 2014
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggioda P_1_6 » mercoledì 6 aprile 2016, 10:44

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?
P_1_6
Prode Principiante
 
Messaggi: 19
Iscrizione: dicembre 2014
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggioda DragonLife » mercoledì 6 aprile 2016, 18:39

P_1_6 Immagine 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
Avatar utente
DragonLife
Scoppiettante Seguace
Scoppiettante Seguace
 
Messaggi: 250
Iscrizione: agosto 2014
Desktop: Unity
Distribuzione: Ubuntu 14.04.1 LTS x86_64

Re: Algoritmi sui numeri primi.

Messaggioda P_1_6 » mercoledì 6 aprile 2016, 19:01

Si c'ho provato ed ho scritto tante di quelle fesserie in buona fede che ho fatto la fine di "Al lupo, al lupo".
P_1_6
Prode Principiante
 
Messaggi: 19
Iscrizione: dicembre 2014
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggioda DragonLife » mercoledì 6 aprile 2016, 21:05

P_1_6 Immagine 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
Avatar utente
DragonLife
Scoppiettante Seguace
Scoppiettante Seguace
 
Messaggi: 250
Iscrizione: agosto 2014
Desktop: Unity
Distribuzione: Ubuntu 14.04.1 LTS x86_64

Re: Algoritmi sui numeri primi.

Messaggioda P_1_6 » mercoledì 6 aprile 2016, 22:12

P_1_6 Immagine 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: 19
Iscrizione: dicembre 2014
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggioda P_1_6 » domenica 3 luglio 2016, 9:16

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: 19
Iscrizione: dicembre 2014
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggioda P_1_6 » sabato 9 luglio 2016, 19:44

Qualcuno lo ha scritto
P_1_6
Prode Principiante
 
Messaggi: 19
Iscrizione: dicembre 2014
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggioda Darren » lunedì 11 luglio 2016, 11:42

xchè non ti metti a cercare le master key dei vari Ransomware virus, "potresti" diventare ricco
Why's life ever easy, or do we make it hard for ourselves?
Avatar utente
Darren
Scoppiettante Seguace
Scoppiettante Seguace
 
Messaggi: 390
Iscrizione: ottobre 2008
Località: skype: nightsky.1984
Desktop: Gnome Shell 3.26.1
Distribuzione: Fedora 27 64bit
Sesso: Maschile

Re: Algoritmi sui numeri primi.

Messaggioda P_1_6 » lunedì 11 luglio 2016, 14:29

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: 19
Iscrizione: dicembre 2014
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggioda P_1_6 » sabato 16 luglio 2016, 10:09

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: 19
Iscrizione: dicembre 2014
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggioda P_1_6 » domenica 17 luglio 2016, 15:17

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: 19
Iscrizione: dicembre 2014
Distribuzione: Ubuntu 15.10 i686

Re: Algoritmi sui numeri primi.

Messaggioda P_1_6 » sabato 26 novembre 2016, 16:07

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
P_1_6
Prode Principiante
 
Messaggi: 19
Iscrizione: dicembre 2014
Distribuzione: Ubuntu 15.10 i686

PrecedenteSuccessiva

Torna a Bar Ubuntu

Chi c’è in linea

Visualizzano questa sezione: 0 utenti registrati e 9 ospiti