Fattorizzazione di N in tempi logaritmici

[P_1_6]

Tutti i numeri sono riconducibili a questo caso:


Input $N$ tale che $N=p*q$ $&$ $p+q-4 mod 8 = 0$ $&$ $(q-p+2)/4=y$ è dispari

chiamando $x$ tale che $8*x+4=p+q$

Algoritmo


$0$ step

$(3 * N-1) / 8 = 3 * x * (x + 1) / 2-3 * y * (y-1) / 2 + (3 * x + 1) * (3 * x + 2) / 2$

$1$ step

$3 * (((2 * (3 * N-1) / 8-3 * y + 1) / 24) + 3 * x * (x + 1) / 2) + 1 = A$

,

$(3 * N-1) / 8 = 3 * x * (x + 1) / 2-3 * y * (y-1) / 2 + (3 * x + 1) * (3 * x + 2) / 2$

,

$3 * (((2 * A-3 * a + 1) / 24) + 3 * x * (x + 1) / 2) + 1 = B$

$2$ step

$3 * (((2 * (3 * N-1) / 8-3 * y + 1) / 24) + 3 * x * (x + 1) / 2) + 1 = A$

,

$(3 * N-1) / 8 = 3 * x * (x + 1) / 2-3 * y * (y-1) / 2 + (3 * x + 1) * (3 * x + 2) / 2$

,

$3 * (((2 * A-3 * a + 1) / 24) + 3 * x * (x + 1) / 2) + 1 = B$

,

$A + 3 * a * (a-1) / 2 = 12 * x * (x + 1) / 2 + 1$

,

$3 * (((2 * B-3 ​​* b + 1) / 24) + 3 * x * (x + 1) / 2) + 1 = C$


$3$ step

$3 * (((2 * (3 * N-1) / 8-3 * y + 1) / 24) + 3 * x * (x + 1) / 2) + 1 = A$

,

$(3 * N-1) / 8 = 3 * x * (x + 1) / 2-3 * y * (y-1) / 2 + (3 * x + 1) * (3 * x + 2) / 2$

,

$3 * (((2 * A-3 * a + 1) / 24) + 3 * x * (x + 1) / 2) + 1 = B$

,

$A + 3 * a * (a-1) / 2 = 12 * x * (x + 1) / 2 + 1$

,

$3 * (((2 * B-3 ​​* b + 1) / 24) + 3 * x * (x + 1) / 2) + 1 = C$

,

$B + 3 * b * (b-1) / 2 = 12 * x * (x + 1) / 2 + 1$

,

$3 * (((2 * C-3 * c + 1) / 24) + 3 * x * (x + 1) / 2) + 1 = D$

$4$ step

.....

.....


e così via

$x,y,A,B,C,D,..... >0$


testando ad ogni step

$0$ step
$y=1$
se $N mod q == 0$ mi fermo ; dove $q=2*(3*x+1-(x-y+1))+1$

$1$ step
$B=A$ e $a=1$
se $N mod q == 0$ mi fermo ; dove $q=2*(3*x+1-(x-y+1))+1$

$2$ step
$C=B$ e $b=1$
se $N mod q == 0$ mi fermo; dove $q=2*(3*x+1-(x-y+1))+1$

$3$ step
$D=C$ e $c=1$
se $N mod q == 0$ mi fermo dove $q=2*(3*x+1-(x-y+1))+1$

.....
.....
e così via



Esempio $N=507$


$3*(((2*190-3*y+1)/24)+3*x*(x+1)/2)+1=A$
,
$190=3*x*(x+1)/2-3*y*(y-1)/2+(3*x+1)*(3*x+2)/2$
,
$3*(((2*A-3*a+1)/24)+3*x*(x+1)/2)+1=B$
,
$A+3*a*(a-1)/2=12*x*(x+1)/2+1$
,
$3*(((2*B-3*b+1)/24)+3*x*(x+1)/2)+1=C$
,
$B+3*b*(b-1)/2=12*x*(x+1)/2+1$
,
$3*(((2*C-3*c+1)/24)+3*x*(x+1)/2)+1=C$
,
$c=1$
,
$x>0$
,
$y>0$
,
$A>0$
,
$B>0$
,
$C>0$









Spiegazione


il logaritmo agisce su $y$ in questo modo

Se $(y + 1) / 2$ è pari $a = - (y-1) / 2$

Se $(y + 1) / 2$ è dispari $a = (y+1) / 2$


Se $(| a | +1) / 2$ è pari $b = - (| a | -1) / 2$

Se $(| a | +1) / 2$ è dispari $b = (| a | +1) / 2$

e così via


per $| a |$ intendo $a$ senza segno



si deve pensare a tutti i numeri fattorizzabili tali che la somma dei loro fattori sia $8*x+4$

esempio

per $x=3$

essi sono

$195$ ha $y$ dispari
$187$ ha $y$ pari
$171$ ha $y$ dispari
$147$ ha $y$ pari
$115$ ha $y$ dispari
$75$ ha $y$ pari

di cui i relativi $M=(3*N-1)/8$ sono
$73$
$70$
$64$
$55$
$43$
$28$

calcoliamoci
$Z=(2*M-3*y+1)/24$ se $y$ è dispari
and
$Z=(2*M-3*(1-y)+1)/24$ se $y$ è pari

$6$
$6$
$5$
$5$
$3$
$3$

ora calcoliamoci $3*(Z+3*x*(x+1)/2)+1$

$73$
$73$
$70$
$70$
$64$
$64$

quindi se vogliamo fattorizzare

$115$ con $y$ uguale a $5$

$3 * (((2 * 43-3 * y + 1) / 24) + 3 * x * (x + 1) / 2) + 1 = A$

$A$ sarà $64$

$3 * (((2 * A-3 * a + 1) / 24) + 3 * x * (x + 1) / 2) + 1 = B$

$a$ sarà $3$ da quanto detto su come agisce il logaritmo e $B=70$

quindi

$A + 3 * a * (a-1) / 2 = 12 * x * (x + 1) / 2 + 1$

$a=3$ $->$ $b=-1$ da quanto detto su come agisce il logaritmo

$3 * (((2 * B-3 * b + 1) / 24) + 3 * x * (x + 1) / 2) + 1 = C$

e $C=73$

quindi

$B + 3 * b * (b-1) / 2 = 12 * x * (x + 1) / 2 + 1$

$3 * (((2 * C-3 * c + 1) / 24) + 3 * x * (x + 1) / 2) + 1 =D$

$c$ sarà $1$ da quanto detto su come agisce il logaritmo

e $D=C=73$

spero di esere stato chiaro


Che ne pensate?

[hydro1]

"P_1_6":Tutti i numeri sono riconducibili a questo caso:


Input $N$ tale che $N=p*q$ $&$ $p+q-4 mod 8 = 0$ $&$ $(q-p+2)/4=y$ è dispari

What??

"P_1_6":
spero di esere stato chiaro

Per niente.

[P_1_6]

"hydro":[quote="P_1_6"]Tutti i numeri sono riconducibili a questo caso:


Input $N$ tale che $N=p*q$ $&$ $p+q-4 mod 8 = 0$ $&$ $(q-p+2)/4=y$ è dispari

What??
[/quote]
un numero dispari è nella forma $4*k+1$ oppure $4*k+3$

il nostro N è nella forma $4*k+3$

ora i $4*k+3$ si suddividono in $(p+q) mod 8 = 0$ oppure $(p+q-4) mod 8 =0$

ora per passare da $4*k+1$ a $4*h+3$ si moltiplica per $3$

per passare da $(p+q) mod 8 = 0$ a $(p+q-4) mod 8 =0$ si moltiplica per $5$

quindi se hai un $4*k+1$ devi moltiplicare per $3$ e per $15$ ed avrai uno dei due nella forma $(p+q-4) mod 8$

se hai un $4*k+3$ devi moltiplicare per $5$ ed avrai uno dei due nella forma $(p+q-4) mod 8$

ora se $y$ è dispari

utilizzi

$3*(((2*(3*N-1)/8-3*y+1)/24)+3*x*(x+1)/2)+1=A$

se $y$ è par utilizzi

$3*(((2*(3*N-1)/8-3*(1-y)+1)/24)+3*x*(x+1)/2)+1=A$

quindi hai $4* log$

"P_1_6":
spero di esere stato chiaro

[quote="hydro"]
Per niente.

[/quote]
in sintesi avrei bisogno di sapere quante soluzioni ha

"P_1_6":
$3*(((2*(3*N-1)/8-3*y+1)/24)+3*x*(x+1)/2)+1=A$
,
$(3*N-1)/8=3*x*(x+1)/2-3*y*(y-1)/2+(3*x+1)*(3*x+2)/2$
,
$3*(((2*A-3*a+1)/24)+3*x*(x+1)/2)+1=B$
,
$A+3*a*(a-1)/2=12*x*(x+1)/2+1$
,
$3*(((2*B-3*b+1)/24)+3*x*(x+1)/2)+1=C$
,
$B+3*b*(b-1)/2=12*x*(x+1)/2+1$
,
$3*(((2*C-3*c+1)/24)+3*x*(x+1)/2)+1=D$
,
.....
.....
e così via

$x,y,A,B,C,D,..... >0$

in funzione del numero di lettere grandi A,B,C,D,E,F,.........

[P_1_6]

Ho modificato il primo post
forse ora si capisce meglio l'algoritmo

[P_1_6]

Ho scritto un paper in inglese
per chi volesse approfondire questo è il link


UPDATE
https://www.academia.edu/44546531/Facto ... hmic_times