Anna Foglino, Francesco Di Noto

Abstract

In this paper we will show an our vedic idea to easy factoring of numbers N = p*q

Riassunto

In questo lavoro mostriamo una nostra idea di natura “vedica”, coerente (cioè con l’omonima matematica degli antichi indiani) per facilitare un po’ la fattorizzazione di numeri composti ed in particolare i numeri semiprimi N =p*q con p e q numeri primi.

°°°°°°°

La matematica vedica che troviamo sul web mostra i modi per effettuare le quattro operazioni aritmetiche, le equazioni ecc. ma offre pochissimi accenni per la fattorizzazione dei numeri composti, cioè con almeno due fattori primi (in questo caso sono noti come semiprimi).
Per le quattro operazioni si rimanda ai siti di matematici di matematica vedica, in particolare ai

Rif. 1 e Rif. 2

In questo breve lavoro divulgativo e di ricerca, mostriamo, oltre ai criteri vedici di divisibilità tramite i metodi aritmetici vedici di Ekadhika e osculazione, una nostra idea “vedica” per rendere più semplice la fattorizzazione all’occidentale, eliminando buona parte del tempo di calcolo detto “a forza bruta”, cioè di dividere N per tutti i numeri primi da 3 fino alla radice quadrata di N numero da fattorizzare; e in particolare se è semiprimo, per qualsiasi scopo (calcolo del M.C.D. e del m.c.m., ecc. ; escludendo però la fattorizzazione dei numeri RSA dell’omonima crittografia, per via dei problemi di lunghissimi tempi computazionali che alla fine si presenteranno anche qui per numeri molto grandi, di centinaia o migliaia di cifre).
In matematica vedica, i numeri N con un numero pari di cifre, si dividono in due gruppi chiamati A e B, risultati finali della moltiplicazione vedica.
Attraverso prove ed errori, abbiamo notato che il numero p primo o composto che sia, è sempre minore di n = √N, per cui deduciamo anche che esso sia della forma A + b, (nessuna connessione con la parte B di N), e con b numero naturale variabile tra 1 e n – A, come vedremo con gli esempi. In questo modo si evita il lungo calcolo a forza bruta fino ad A, e non è poco , specialmente quando b è piccolo (nei numeri semiprimi N che cominciano con 7, 8 e 9 , molto vicini alla potenza di 10 successiva; il che significa differenze piccole o loro prodotto anch’esso piccolo e facilmente fattorizzabile).

Vediamo con alcuni esempi, per poi infine trarne alcune conclusioni e possibili osservazioni per migliorare eventualmente questa nostra idea di base.

Idea generale

p ≈ A + b con b numero naturale (molto spesso un fattore di B, compreso B stesso specialmente se è primo, ma anche se a volte è composto) fino a quando A + b divide N e quindi q = N/(A+b)
Esempi vari
320352 = 376*852

320 352

A =320 B = 352
A + b non divide N fino a b = 56 (quindi 56 tentativi contro i totali 376 a forza bruta, prima di arrivare a 376).
Con la fattorizzazione a forza bruta (dividere N per tutti i numeri primi fino alla radice quadrata di N) occorrono:
n =√320352 = 565,99
π (565) = 565/ln(565= 565/6,33 = 89 tentativi totali, poiché partiamo già da 320; rimangono da testare i numeri primi da 320 a 565 che sono 565 – 320 = 245, e 245/ln (565) = 245/6,33= 38,70, circa 38 numeri primi in cui trovare p nel caso p fosse primo, ma non lo sappiamo a priori. In questo caso, b va da 1 a 56 partendo da A = 320.
Infatti, ritornando alla nostra idea, valida anche per fattori non primi, i casi più comuni,
320 +1 = 321, ma 320352 non divide 321, poiché:
320352/321 = 997,98 non intero
….
….
— dopo 55 tentativi , troviamo 56, la soluzione:
320 +56 = 376 , poichè 320352/376 = 852 intero, e quindi fattore composto di N, equivalente a q se fosse primo. Il numero cercato è quindi b = 56, affinché N divida esattamente A + b dando l’altro fattore, q = 852
Ma anche con B = 352, si arriva addirittura anche prima, con 352 + 24 = 376 (cosa da controllare in seguito con altri numeri N.
Altro esempio:
888*997 = 885 336 (la cui cifra iniziale 8 è indizio di vicinanza dei due fattori o anche uno solo di essi è prossimo a 1000 =3^10), ma lo scopriremo solo a fine fattorizzazione.

Infatti in questo caso il numero b è molto piccolo,

3 ( = 1000 – 997), e anche fattore di 336 ( prodotto di 3 e 112 fattori di B).

Per cui dopo soli tre tentativi abbiamo

A + b = 885 + 3 = 888, uno dei grandi fattori di N, l’altro fattore piccolo di B ovviamente è 112, tale che 3*112 = 336 = B e 885 *112 = 997, l’altro grande fattore (primi no non importa).
997 si trova ovviamente anche con 885336/888 = 997, e la fattorizzazione è fatta con soli 3 tentativi!

Infatti, vediamo la fattorizzazione vedica:
con un esempio regolare con N a sei cifre due, e fattori non primi

888*997 = 885 336

Prodotto vedico

888   -112 differenza diagonale 885

997       -3   differenza diagonale 885

885   336

Da cui

p = 885 +3 = 888

q = 885+ 112 = 997

e fattorizzando 336 abbiamo 1*2^4 *3*7

con 112 prodotto dei fattori rimanenti 1*2^4 *7

Quando uno dei fattori inizia con la cifra 9, come per esempio 997 di questo caso, la differenza con la successiva potenza di 10, in questo caso 1000^3, è piccola e quindi la fattorizzazione è più semplice, come pure quando B è il prodotto di due numeri primi, ma non sempre, ci sono eccezioni.

Qualche esempio in cui B è numero primo

N =3861= 39*99 non primi, ma 61 è primo

A = 38 = differenza diagonale, B = 61 numero

primo, quindi 1*61

p = 38 +1 = 39

q = 38 + 61 = 99

Un esempio con B = p*q prodotto di due numeri primi:

Esempio per N =7469 = 77*97
A = 74 B = 69 = 3*23 = f’ * f’’
Applicando direttamente le
q = A + f’ (1)

p = A + f’’ = (2)
abbiamo

p = 74+3 = 77

q = 74+23 = 97

e la fattorizzazione è fatta!

74 è A = differenza diagonale nel prodotto vedico:

77 77 – 100
97 97 -100
77      -23  differenza diagonale 77- 3 = 74 = A
97       – 3  differenza diagonale 97 – 23= 74 = A
74       69

7469 = N = unione di A e B.

Da N = 7469 siamo risaliti giunti velocemente a p

e a q a ritroso con il nostro algoritmo

(fattorizzazione del numero B) basato sulla

moltiplicazione vedica.

Ma ci sono anche numeri dello stesso tipo ma con

alcune difficoltà per la fattorizzazione vedica, e

chiameremo irregolari. Un solo esempio:

727 *983 = 714 641= N

Prodotto vedico :

727      -273 differenza diagonale 710
983        -17 differenza diagonale 710
710     4641

Fattorizzazione di B = 641:     641 =1*641 è primo

710+641 = 1351

710 +1 = 712

Numeri che non dividono n, quindi il caso è anomalo, poiché nella sua fattorizzazione vedica spunta uno zero intruso tra 71 e 4641 di N = 714641 che ostacola la stessa fattorizzazione vedica.

La fattorizzazione giusta ora è 4641= 17*273

tale che 710 +17 = 727 e 710 +273 = 983

In questo caso A è uguale a 71 *10 = 710 e

B = 4641 = 641 preceduto dall’ultima cifra ( 4) di

A = 714 . Ma ci potrebbero essere molti altri casi

con questa irregolarità, e saranno eventualmente

studiati in seguito.

Altri esempi:
457*821 = 375197

Fattorizziamo 197, = numero primo

A +1 = 375 +1 = 376 ≠ 457
A+ 197= 572 ≠ 821

Quindi non funziona sempre quando B è primo.

Prodotto vedico:

457      – 543     d = 278 = 457-179
821        -179     d= 278 = 821-543
278     97197

Il prodotto vedico 27897197 non è però 375197 con la moltiplicazione occidentale, ma condividono il numero primo finale 197, ma nasconde i veri fattori di 375197, infatti

278+179 = 457 = p

278 + 543 = 821 = q

Mistero della fattorizzazione vedica, ancora tutto da risolvere…

Altro esempio

821*993 = 815253

253= 11*23

815+11 = 826 circa 821 diff. 5

815 + a con a da 1 a 11. In questo caso a = 6 tale che 815 + 6 = 821 = p

Confronto con congettura della mantissa

N = 815253, n = 902,91

902*0,91= 820, 82 circa 820 diff. 1, quindi un solo

tentativo 820 +1 = 821 = p

e q = N/p =815253/821 =993

Quindi a volte è meglio la nostra quasi congettura della mantissa (quasi poiché ci sono dei contro esempi, eppure sempre più rari al crescere della mantissa).

Per i criteri vedici di divisibilità, riportiamo il concetto vedico e l’uso dell’Ekadhica:

Ekadhica

L’Ekadhica di un numero è il numero successivo al numero che precede 9. Si trova pertanto utilizzando il Sutra Per Uno in Più del Precedente.
Quindi il numero deve finire per 9.
Ekadica di 19 è 2. L’Ekadhica di 49 è 5 l’Ekadhica di 119 è 12.
Se il numero non finisce per 9 basta moltiplicare il numero per un numero in modo che si abbia 9 alla fine.
Quindi se voglio avere l’Ekadhica di 7 moltiplico per 7.
Quindi ho 7×7=49 e quindi l’Ekadhica è 5
Se ho 23 moltiplico 23×3 e ho 69 quindi l’Ekadhica e 7.
Ekadhica è il numero che precede il 9, più 1
Osculazione
L’Ekadhica si usa nel metodo di osculazione: è un metodo generale per trovare la divisibilità di un numero.
Esempio
Vogliamo sapere se 84 è divisibile per 7
1) Troviamo l’Ekadhica di 7. Poiché 7 non finisce per 9, lo moltiplichiamo per 7 quindi abbiamo 7*7=49. L’Ekadhica
di 49 è 5 = 4 +1 .
2) Per osculare 84 moltiplichiamo la sua ultima cifra 4 per l’Ekadhica 5 e aggiungiamo il risultato alla cifra (8) che lo precede
3) E otteniamo 4*5 +8= 28.
4) Dividiamo 28 per 7 = 4; 28 è divisibile per 4 e quindi anche 84 è divisibile per infatti 84/7 = 12

Quindi 4×5 = 20 poi sommo 20 a 8 e ottengo 28 che è divisibile per 7 quindi 84 è divisibile per 7.
Posso continuare il metodo dell’osculazione con il risultato ottenuto, e
poi ancora fino a quando voglio.

Osculazione di 28.

Osculazione di 42

Osculazione di 14

Osculazione di 21

Posso andare avanti e osculare il 7 pensandolo come 07 e continuare.
In questo modo ottengo multipli di 7.

Esempio 2
Proviamo a vedere se 285 è divisibile per 19.
1) L’Ekadhica di 19 è 2
2) Osculiamo 285 con 2

Poiché 19 è chiaramente divisibile per 19, 285 è divisibile per 19

Insomma è un criterio di divisibilità per 7 diverso da quello occidentale (da Wikipedia, voce “Criteri di divisibilità”:
Divisibilità per 7
Un numero è divisibile per 7 se la somma tra il numero ottenuto escludendo la cifra delle unità (prenumero) e il quintuplo della cifra delle unità (coda numerica) è 7 o un multiplo di 7.
Esempio: 68089; calcoliamo 6808 + 9×5 = 6853; non sapendo se 6853 sia divisibile per 7 basta ripetere la procedura. 685 + 3×5 = 700, che è evidentemente un multiplo di sette. Pertanto 68089 è multiplo di 7.
Applichiamolo a 84: calcoliamo 8+ 5*4 = 28 28 è divisibile per 7 ( 28=4*7) quindi lo è anche 84 con 84 =12*7) . Quindi i due criteri, vedico e occidentale, portano allo stesso risultato pratico.
Insomma, possiamo dire benissimo che ogni numero composto p*q nasconde in qualche modo nelle sue cifre, specialmente le ultime, il fattore più piccolo, e i due criteri di divisibilità (vedico e occidentale) servono ad “estrarlo” più o meno velocemente senza ricorrere alla divisione diretta o la “forza bruta” per numeri primi più grandi, per i quali non si conoscono ancora specifici criteri di divisibilità.

Per questi e più grandi numeri primi, ci sono invece i metodi di fattorizzazione: per esempio l’algoritmo di Fermat in Occidente, la fattorizzazione vedica nella omonima e antica matematica, che abbiamo visto sopra e anche qui si seguito. Anche questi numeri primi più grandi, come vedremo, si nascondono bene nelle cifre del loro prodotto, come quelli più piccoli, ma potrebbero anch’essi estraibili, senza forza bruta (solo in qualche caso, per esempio con B primo, ma non sempre) o con il meno possibile, con B piccolo e suoi fattori ancora più piccoli, come prima visto per numeri composti con cifra iniziale 8 oppure 9. Per la fattorizzazione vedica, riporto anche questo brano, con qualche esempio (Da Anna Foglino):

La formula

Per fattorizzare n

n=a2+r (con r>0), se esiste un numero b tale che 2a+1−r=b2, allora n=(a+1+b)(a+1−b).
vuol dire

Equivale a

Qui mi viene l’idea che , b, a+1 e , a+1, b sono una terna pitagorica per cui la fattorizzazione potrebbe essere anche fatta in questo modo e possiamo avere 3 casi
1) e quindi abbiamo
2) e quindi abbiamo
3) Altri casi
Proviamo con qualche esempio
Quindi nei primi casi abbiamo a che vedere con dei quadrati perfetti
Caso 1
Per fattorizzare 7056 troviamo per cui 7056 = (84+1) () = 85×13
Caso 2
Per fattorizzare 3969 troviamo = 63 per cui 3969 = (63 + 2 )())= 65 x 16
Poi ci possono essere gli altri casi sempre con che però non rientrano in questi casi.
Altri casi sono quelli che hai proposto tu.
Un’idea per velocizzare potrebbe essere quella di introdurre l’Ekadhica.
Voglio fattorizzare
4221 = 63×67
Considero 42
= 6,48
Quindi ho
42+1 …. 42+21 cioè 22 tentativi
Uso dell’Ekadica
Cos’è l’Ekadhica
E(19) = 2 il numero successivo al numero che precede 9
E(7) = E(7×7)= E(49) = 5

Per vedere se 43 è un divisore di 4221 cerco l’Ekadhica di 43 che è 13
Faccio l’osculazione e trovo

4 2 2 1
114 68 15
Quindi non è divisibile per 43 e posso andare avanti in questo modo
Ekadhika di 63 è 19

4 2 2 1
63 23 21

L’ultimo numero 63 è divisibile per 63
Per i numeri che ha hanno cifre dispari si potrebbe usare il modello della moltiplicazione inversa verticale ed incrociato .. ma dovrei approfondire se funziona

N=pxq
Se n= a b c
p      q
r       s
________
a   b   c

Dove i fattori si trovano come pxr, pxs+qxr, qxs

Con la nostra idea A + f’ con f’ =B stesso =21

anche se non numero primo, abbiamo

42 +21 = 63 = p, uno dei fattori , l’altro è 67.

Altro esempio con un numero N di otto cifre:

Altri esempi di fatt. vedica con numeri di otto cifre

29513736 * 92842033 = 274 015251665288= N

prodotto vedico
29 513 736 -70486264 diff.diag. 22355769

92 842 033 – 7157967 diff. diagonale 22355769
22355769 504338352665288

Metodo A+ b = 274 006 49 + 213087 = 29513736 = p

Conclusioni

Possiamo concludere provvisoriamente che l’idea non è proprio semplicistica o del tutto errata come potrebbe sembrare a prima vista, ma fondata sulla base nella matematica vedica, tramite i concetti di A e B come prima parte e seconda parte dei numeri N con cifre pari (rimane da risolvere il problema dei numeri dispari, ai quali penseremo successivamente, per poterlo scindere in A e B con numero diverso di cifre, per esempio 29083 = 127*229 con A = 29 e B = 83 entrambi molto lontani da 127 e da 229, e simili).
Come già detto, i fattori primi e non primi di un numero composto N = p*q, si nascondono tra le cifre di N, specialmente tra le ultime), e nelle loro relazioni aritmetiche: in Occidente ci sono solo i noti criteri di divisibilità per estrarli, nella matematica vedica ci sono analoghi criteri (Ekadhika e osculazione), ma soprattutto la formula A + f’ con f’ uno dei fattori di B, o anche B stesso se è primo o anche no in qualche caso (per esempio 4221 = 63×67 con 63 = 42 + 21, a meno che non si tratti di fortuita coincidenza, cosa che si vedrò con ulteriori ricerche su molti altri numeri composti).

Riferimenti

1 – Matematica Vedica Matematica Vedica – Il primo sito italiano sulla …
matematicavedica.com/

2 – Progetto Polymath – Matematica Vedica
https://areeweb.polito.it/didattica/polymath/htmlS/…/Matematicae/Dic_07/Vedica.htm

3 – Alex Bellos, “Il meraviglioso mondo dei numeri” Einaudi, 2011, Capitolo terzo

Caltanissetta 1 . 4. 2018