Fattorizzazione

Question

Per la miglior risposta c'è una piccola ricompensa 0.003 BTC (BITCOIN)

Per ogni numero H=a*b && (b-a) mod 8 == 0

K=(H-1)/8 ed n=b-a

è vera una di queste tre

1

solve (H-1)/8=3*x*(x+1)/2-3*y*(y-1)/2+(3*x+1)*(3*x+2)/2

2

solve (H-1)/8=3*x*(x+1)/2-3*y*(y-1)/2+(3*x-1+1)*(3*x-1+2)/2-(x-y+1)

3

solve (H-1)/8=3*x*(x+1)/2-3*y*(y-1)/2+(3*x-2+1)*(3*x-2+2)/2-2*(x-y+1)

Osserviamo in particolare la 1 :

H =0 mod 3

quindi H/3=N=p*q

dove p=[2*(3*x+1-(x-y+1))+1-(4*y-2)] and q=[2*(3*x+1-(x-y+1))+1]

e p+q = 4 mod 8

H ha la caratteristica che

H-1 = 0 mod 8

e

((H-1)/8-1)=0 mod 3

riscriviamo p in funzione della sola x dove M=(H-1)/8

solve

p=[2*(3*x+1-(x-y+1))+1-(4*y-2)]

,

3*x*(x+1)/2-3*y*(y-1)/2+(3*x+1)*(3*x+2)/2=M

ed avremo

p=[12*x+6-sqrt[3*(48*x^2+48*x+11-8*M)]]/3

A=((H-1)/8-1)/3

A ha la caratteristica che

A-(x-1)*p=((p*3*p*3-1)/8-1)/3-p*(p-3)/2

ed in un intorno c di p, x sarà molto vicina (d) ad x0 quindi

If N=p*q e (p+q-4) mod 8 =0 e p >= (p+q)/4

N=66390187

(3*N-1)/8=24896320

((3*N-1)/8-1)/3=8298773

8298773-((x+d)-1)*(p-c)=(((p-c)*3*(p-c)*3-1)/8-1)/3-(p-c)*((p-c)-3)/2

,

c=1/100000000

,

p=[12*x+6-sqrt[3*(48*x^2+48*x+11-8*24896320)]]/3

to vary d in

d=1/10000000000

or

d=2/10000000000

or

d=3/10000000000

or

d=4/10000000000

or

d=5/10000000000

or

d=6/10000000000

or

d=7/10000000000

or

d=8/10000000000

or

d=9/10000000000

or

d=10/10000000000

for d=6/10000000000 -> x0=2078 and x=2075,.....

La mia domanda è:

Quale ordine di grandezza devono avere d e c nei confronti di p ed N e tra di loro?

Autore

Risposta

P_1_6

(@p_1_6)

159 punti

livello:

Livello 1

46 Risposte
5 2 36

14/03/2020 15:07

P_1_6 · Accepted Answer

fissato c=1d varia 1/1000 a 10/1000 prendiamo ad esempio RSA100 del RSA challengeovvero N=1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139ep=37975227936943673922808872755445627854565536638199fissato c=1 e d=6/1000si avràp=37971842487510905738141966493450770567321799011750fissato c=1 e d=69/10000si avràp=37971842487510905738141966493450770567321799011750fissato c=1 e d=697/100000si avràp=37974719469178671266284710224709855430279733686466fissato c=1 e d=6976/1000000si avràp= 37975151072833117622027527562395939271938326543614fissato c=1 e d=69764/10000000si avràp=37975223008206280989373698913587627859700782422577ecc.ecc.quindi come potete notare non si risolve la fattorizzazione in tempi computazionalmente accettabili ma questo quesito si poteva risolvere e potevate vincere i 0.003 BTC   spero che qualcuno smentisca il mio contenuto in modo tale da avere ancora speranze

ArtemSavka96 · Answer

Sarò io che non ho capito bene, ma potresti spiegare meglio il "problema"

Moe · Answer

Forse sarò io che sbaglio a capire ma non mi trovo con la tua definizione iniziale. In poche parole hai detto che:

$\forall$$a$,$b$ $\bigl($ $a$$b$ $\space$ $\land$ $\space$ $b$ $-$ $a$ $\bigr)$ sono $congrui$ a $0$ $\bigl($ $mod$ $8$ $\bigr)$. In formule potremo scrivere :

$\forall$$a$,$b$ $\in$ $Z$ $\bigl($ $\space$ $\bigl($ $ab$ $\equiv_{8}$ $0$ $\bigr)$ $\land$ $\bigl($ $b$ $-$ $a$ $\equiv_{8}$ $0$ $\bigr)$ $\space$ $\bigr)$.

Ma ciò significa che $\forall$$a$,$b$ $\in$ $Z$ $\bigl($ $ab$ $\equiv_{8}$ $b$ $-$ $a$ $\bigr)$ dunque questi due numeri risultano avere lo stesso resto della divisione. Ma non sempre è così.

$Controesempio$

$\bigl($ $\exists$ $a$,$b$ $\in$ $Z$ $|$ $ab$ $\not \equiv_{8}$ $b$ $-$ $a$ $\bigr)$ :

Con $a$ $=$ $8$ e $b$ $=$ $7$ abbiamo che $ab$ $=$ $56$ $\land$ $b$ $-$ $a$ $=$ $-1$. Se supponiamo che siano congrui allora si avrà $56$ $\equiv_{8}$ $-1$ $\iff$ $\bigl($ $\exists$ $m$ $\in$ $Z$ $|$ $57$ $=$ $8m$ $\bigr)$

Ma $57$ non è un multiplo di $8$. Quindi abbiamo ottenuto una contraddizione. Ciò implica necessariamente che esistono $ab$ e $b$ $-$ $a$ tali che non siano congrui.

Moe

(@moe)

1272 punti

livello:

Livello 2

223 Risposte
9 158 50

26/03/2020 14:40

Vi94 · Answer

Vedo che stai utilizzando un metodo. Sei in MATLAB?

[Risolto] Fattorizzazione

Domande