numeri primi

[Diego]

buongiorno, trovandomi a fare un programma dedicato alla criptografia di messaggi mi è sorto un dubbio che ora vi espongo:
è possibile risalire dal rapporto di due numeri primi alla coppia di questi numeri?
esempio: 0,395348837...
(17/43)
questa coppia è facile da trovare a tentativi ma esiste un metodo generale?

[Pasquale]

Direi che qualsiasi numero decimale, se ha un periodo, è generato da un rapporto fra due numeri, fra cui il denominatore primo ed il numeratore anche non primo, purché non multiplo: siamo nel campo dei numeri razionali.
Se invece un decimale non ha periodo, non esiste una frazione generatrice e siamo nel campo dei numeri irrazionali.
Quindi se tu hai un decimale e vuoi risalire alla frazione generatrice, devi individuare il suo periodo.
Non conosco la criptografia, ma mi è capitato di leggere che per dare inaccessibilità a ciò che si vuole difendere, si utilizzano numeri primi molto grandi, che generando periodi formati da moltissime cifre renderebbero più difficoltosa la possibilità di scardinare il sistema.
E' evidente che per trovare la frazione generatrice di un decimale con un periodo lunghissimo, non è possibile farlo ad occhio o con una formula, ma occorre un calcolatore in grado di lavorare su grandissimi numeri e con molto tempo a disposizione: di qui si è scatenata la lotta fra calcolatori, ma anche la lotta nella ricerca di primi sempre più grandi non alla portata degli ultimi calcolatori, così come la lotta nella realizzazione di calcolatori in grado di lavorare sull'ultimo primo più grande conosciuto. Lo stesso dicasi relativamente all'uso in questo campo dei numeri irrazionali ed irrazionali trascendenti che non hanno una frazione generatrice, tipo quelli derivati da una radice, o come il pigreco: anche qui, chi trova più cifre del pigreco batte l'ultimo calcolatore fermo al record precedente.
Ora non so se ciò che chiedi si riferisce a qualcosa che gira intorno a questa problematica. Se cerchi genericamente la frazione generatrice di un numero periodico razionale, la formula esiste e penso che tu la conosca, ma se il periodo contiene molte cifre, per trovarlo devi utilizzare un computer capace di trattare grandi numeri. Se invece devi trattare numeri abbastanza grandi e tuttavia alla portata del tuo computer, allora stai cercando una routine che ti consenta di trovare il periodo.
Dunque, se ho capito il senso della tua ricerca e se non ho detto stupidaggini, dicci di più sul tuo problema e se ha attinenza con quanto sopra, ovvero se vai alla ricerca di una routine, oppure se vuoi sapere se altri siano in grado di farlo, ovvero quale sia il grado di sicurezza che puoi realizzare per l'oggetto del tuo studio.

[Diego]

Grazie per aver risposto intanto, se il problema dunque sta nel riuscire a trovare il periodo allora mi servirebbe un trucco o una tecnica per riuscire a conoscere delle coppie di numeri primi il cui rapporto abbia tante cifre del periodo quante il valore del denominatore meno uno, mi spiego: è stato dimostrato che il rapporto tra due numeri primi (x,y di cui y il denominatore) non ha sicuramente più cifre del periodo rispetto a y-1:

come faccio però a essere sicuro che abbia y-1 cifre del periodo se non posso permettermi di calcolare il rapporto per l'enormità dei numeri?

[Pasquale]

Un momento: cosa conosci, i due numeri della frazione o il rapporto? Oppure non conosci nulla? Non potresti dire qualcosa in più che chiarisca meglio i termini del quesito?

[Diego]

Ciao Pasquale,
voglio trovare delle coppie di numeri primi tali che il loro rapporto abbia un numero di cifre del periodo pari al valore del denominatore meno uno.
In modo che sia difficile dalla frazione risalire ai due numeri primi da cui è stata generata.


Diego

[Pasquale]

Va bene, nel frattempo ho effettuato delle osservazioni sulla tipologia delle frazioni n/d e ne ho dedotto quanto segue:

effettivamente il periodo massimo possibile non supera la lunghezza di d-1, per cui quello che conta è il denominatore d;

occorre però tener presente che non tutti i rapporti del tipo considerato determinano con certezza un periodo lungo quanto d-1: in particolare, ho notato che essendo d-1 non primo, il periodo potrebbe essere lungo quanto un suo divisore (a volte si, a volte no); quindi la lunghezza del periodo andrebbe testata.

Allora, una volta individuato un primo d lungo quanto più possibile, cioè trattabile con gli strumenti disponibili, andrei alla ricerca di altro primo n, tale che n/d possa generare un periodo lungo d-1 e non quanto un suo divisore ( è questa la cosa da testare).

Diversamente potresti scegliere semplicemente un qualsiasi primo lungo abbastanza, facendo finta che sia il periodo generato in un rapporto n/d ignoto anche a te e replicarlo continuamente come in un finto periodo. D'altra parte, se tu vuoi generare un rapporto con n e d a te noti, è possibile che altri dal rapporto possano risalire ad n e d, dal momento che il dato lunghezza di d sarebbe già noto.

Magari potresti costruire un periodo non periodo, formato cioè da una certa quantità di cifre generate in modo casuale, successivamente ripetute più volte, dopo averle opportunamente rimescolate: anche qui, quale sarebbe la frazione generatrice? Se poi è necessario che tu debba conoscerla obbligatoriamente, allora non vedo che la prima soluzione, ma non so se altri del forum hanno da dire altro sulla questione. Aspettiamo.

[Info]

interessante..... io direi quasi di riempire casualmente il numero di decimali fino ad n... poi aggiungere la lunghezza del periodo ((-; per te poi è comodo tornare indietro facendo una trim dei primi k caratteri (numero letto dalle cifre dopo n).

per esempio $\frac13=0_\cdot333_{\cdots}$ per noi sarebbe 0.3671 con 6 e 7 numeri càsuali ed 1 lunghezza del periodo.

cosa ne pensi?

[Diego]

Grazie a tutti

[Pasquale]

Info, quanto dici servirebbe per camuffare il rapporto, ma consentire all'autore di ricostruirlo, per poi giungere ad n e d giusto?
Se così è, naturalmente ognuno può costruirsi una regola a propria fantasia per proprio conto, per evitare che possa essere scardinato il sistema di criptaggio.
Non è detto magari che sul periodo generato da n/d non si possa effettuare ad esempio una trasformazione del tipo periodo x altronumeroprimo: in tale caso, una volta risaliti alla lunghezza di quello sarebbe stato il periodo, bisognerebbe prima effetuare una divisione per ottenere il vero periodo.
Un'altra cosa: il tuo ultimo numero di controllo ha una sola cifra, perché hai fatto un esempio semplice, ma nella realtà sarebbe formato da più cifre, perché magari il periodo è lungo 1231 cifre: quindi in tutto ci sarebbe il periodo + i casuali + il numero finale, al quale aggiungerei la quantità di cifre del numero finale. Si potrebbe anche capovolgere il significato: periodo + casuali + numeroquantitàcasuali + numero quantitànumeroquantitàcasuali.
Oppure: casuali + periodo + casuali + ..........

Per Diego: grazie per il ringraziamento, ma chissà se hai trovato la risposta che cercavi ?

[Info]

ciao PAsquale,
il numero finale avrebbe comunque un numero fisso di cifre, 1231 cifre vorrebbe dire numero fisso di 4 cifre.
Periodo di 15 cifre, per esempio, lo scriverei 0015.... altrimenti diventa troppo incasinato anche per lui risalire al periodo

ed il numero finale avrebbe comunque un numero fisso di cifre, per ogni frazione

[Pasquale]

Si Inf, mi ero lanciato in fantastiche elucubrazioni a briglia sciolta, come in un sogno criptico.

[Info]

ahahahah ti faro`un esempio con il numero di Diego

$\frac{17}{43}=0,395348837_\cdots$

per noi sarebbe

$0,395348837\underbrace{4567876543456787654343789765467896}\underbrace{09}$

con 34 numeri casuali (43 - 9) e lunghezza periodo in 2 cifre

questo quello che intendevo

[Pasquale]

Bene, facciamo una prova: NDHHPDPWZRIVIPXPWXYDCPHW (frase 8,2,7,7)

[Info]

Pasquale... non ho capito nulla della tua frase... dovresti dare a Diego la frase in chiaro, e lui poi cifrartela in base alla discussione.... no?

[Pasquale]

A dire il vero, Diego ha salutato e ringraziato, ritenendo di aver chiarito il suo problema, che riguardava la difesa dello scardinamento di un sistema cripto (mi pare di aver capito), nell'ambito di un suo studio sull'argomento.

In questa fase invece sono io che ho iniziato ad interessarmi del problema, cercando di mettere su un sistema cripto personale, inaccessibile a chiunque.

Dunque, questa è la $\text { }$grande sfida:

Chiunque riuscirà a decriptare la mia frase nell'arco di anno a partire da oggi, riceverà l'interessante "premio cripto" da me testè istituito.

Indizi: la frase è composta da 6 parole (8,2,7,7,2,10), oltre gli spazi fra una parola e l'altra, ed ha a che vedere con le cifre decimali del pigreco.

Di più non posso dire e quella che segue è la frase criptata (compresi gli spazi):


$\text { }$UQQ&Ub%S?aS|ç|bT&%ST>UL&Q%Sf&SQ>&TLUrr&%}


$\text { }$


Scusate, solo adesso mi rendo conto che col sistema con cui l'ho elaborata non sarà mai possibile decriptarla, per cui, siccome il premio lo voglio dare, cambio la frase con questa, elaborata con un sistema più semplice:

4gii7g){CuECkNk)}7{C}<g+7i{Cj7Ci<7}+g557{C}k<Cvkjk<kCNkC4uEz7{Eg

Niente paura, non è la lunghezza che conta, ma il criterio con cui è stata criptata.

Indizi: frase (8,2,7,7,2,10,3,6,2,8). Più in là potrò fornire a gentile richiesta anche la chiave con funzione di password, ma anche con quella penso che non sarà possibile riuscirci e finirà che dovrò fornire tutta la routine di decriptazione

ATTENZIONE: come si vedrà appresso le due frasi sono da considerare annullate; resta però in piedi il premio cripto.