mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Alberico Lepore (https://www.mersenneforum.org/forumdisplay.php?f=166)
-   -   WG FACTORIZAZION in polynomial time (https://www.mersenneforum.org/showthread.php?t=27450)

Alberico Lepore 2022-01-01 15:04

WG FACTORIZAZION in polynomial time
 
Happy New Year !

WG FACTORIZAZION in polynomial time

Languages [ITA-MATH]
[url]https://www.academia.edu/66788027/Fattorizzazione_wg[/url]

What do you think?

Alberico Lepore 2022-01-03 14:02

[QUOTE=Viliam Furik;597010]Maybe if you provided an English text with some example of usage, preferably not located at an external link, that would be nice.[/QUOTE]

the mathematical procedure is correct.
Only that it is computationally impossible to find a suitable B.
I am already studying another method which, as you suggested, I will write in English and show the example.
Sorry for the inconvenience.

Alberico Lepore 2022-01-03 14:21

more less I'm studying this:



to factor N = 27 * 65

you have to choose (65-p) mod 8 = 0

and

you have to choose (q-27) mod 8 = 0

suppose we choose 41 and 43

41 * 43 = 1763

the following W and w are in the form

W = 65 * n + (1763 - 27 * 65) / 8

w = 27 * m + (1763 - 27 * 65) / 8



(1763-3) / 8 = 220


220 - W- [4- (65-7) * (65-5) / 8] = 65 * X

W = - ([COLOR="blue"]65[/COLOR] * n + 1) = q * (65-p) / 8, p * q = 1763

q = [COLOR="Red"]27[/COLOR]-8 * n


220 - w- [4- (27-7) * (27-5) / 8] = 27 * X

w = ([COLOR="red"]27[/COLOR] * m + 1) = p * (q-27) / 8, p * q = 1763

p = [COLOR="Blue"]65[/COLOR]-8 * m


Later I test if binary search can work

Alberico Lepore 2022-01-05 13:20

[QUOTE=Alberico Lepore;596803]Happy New Year !

WG FACTORIZAZION in polynomial time

Languages [ITA-MATH]
[url]https://www.academia.edu/66788027/Fattorizzazione_wg[/url]

What do you think?[/QUOTE]

mi è venuta un IDEA

N*25^F=(a*5^F)*(b*5^F)

scegliere B != 5*J


quando arriveremo alla forma

(t^2+u*t+v) mod (B^2) = 0


t=n*(a*5^F)

Z=n*a

25^F*Z^2 +5^F*Z+v mod (B^2)

se v=5^J

riformuliamo il tutto

(t^2+u*t+v) mod (5^J*B^2) = 0

e vediamo se rientra in coppermisth method

Alberico Lepore 2022-01-06 15:18

[QUOTE=Alberico Lepore;597189]mi è venuta un IDEA

[/QUOTE]


PROOF of factorizazion in polynomial time [8 digit]

reference

PART I
[url]https://www.academia.edu/48848013/Lepore_Factorization_nr_88[/url]
&
[url]https://www.academia.edu/66788027/Fattorizzazione_wg[/url]


Supponiamo di voler fattorizzare N=9967*6781=67586227

A=sqrt(N) B=2*sqrt(N/2)

log_5(2*sqrt(N/2))=log_5(11631)=6

67586227*25^6=16500543701171875

A=sqrt(N) B=2*sqrt(N/2)*25^6

C=A D=(B+8)*25^6


Scegliamo
A=8821 B=11631*25^6
C=8821 B=11639*25^6


solve
N=16500543701171875
,
M=(8821)*11631*25^6
,
H=(8821)*11639*25^6
,
(M-3)/8-(a*n+(M-N)/8)-[4-(a-7)*(a-5)/8]=a*(a+11631*25^6-12)/8
,
(H-3)/8-(a*m+(H-N)/8)-[4-(a-7)*(a-5)/8]=a*(a+11639*25^6-12)/8

->m=n-244140625


solve
N=16500543701171875
,
M=(8821)*11631*25^6
,
H=(8821)*11639*25^6
,
(M-3)/8-(a*n+(M-N)/8)-[4-(a-7)*(a-5)/8]=a*(a+11631*25^6-12)/8
,
(a*n+(M-N)/8)*(a*(n-244140625)+(H-N)/8)=X
,
a*n=t
,
a,X

->

11631^2*25^12*X=t^2+2136891113281250*t+1141575907505095005035400390625

Use Coppersmith method

PROOF

t=6781*(9967*25^6-11631*25^6)/8

-t=344347656250000<11631^2*25^12


All times are UTC. The time now is 11:38.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.