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]

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]

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
&

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.