Notifiche
Cancella tutto

[In evidenza] Fattorizzazione  

  

6

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?

 

1
22
2

 

Se può essere d'aiuto vi mostro i tre schemi

La prima immagine è lo schema che identifica tutti i numeri (H-1)/8
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)

guardate le diagonali

La seconda immagine è lo schema della 3 di A=((H-1)/8-1)/3

La terza immagine è lo schema di A-(x-1)*p=((p*3*p*3-1)/8-1)/3-p*(p-3)/2

Topic Tags
4 Risposte
3

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

@artemsavka96

Esempio

Se N ha 1000 cifre e p 500 cifre e c=1/(10^t) e d=Z/(10^s) con Z da 1 a 10

che valore devono avere s e t ?

 

Potresti scrivere meglio la traccia, così cerco di scrivere un programma in grado di calcolare il problema,

Grazie e scusa se al momento nessuno è in grado di risponderti. 

@artemsavka96 per l'analisi è sufficiente prendere gli N fattorizzabili i cui fattori (non necessariamente primi) p e q soddisfano

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

poi fissato c si fa variare d qui

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

,

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

ed il tuo d è quello che manda x più vicino ad x0

x0 te lo calcoli qui

((3*N-1)/8-1)/3-(x0-1)*p=((p*3*p*3-1)/8-1)/3-p*(p-3)/2

 

da tanti numeri analizzati viene fuori la soluzione

non esitate a far domande

 

Rileggendo l'esempio, sto pensando che s e t possono essere valori oltre 100, nel senso 

C= 1/10^100

D=z/10^100

O di questo tipo, cioè penso che per N e p tendenti all'infinito, c e d devono essere infinitesimi,

Onestamente non so più come posso esserti utile

@artemsavka96 grazie per la tua passione 

2

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.

 

@giandomenico 

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

 

do il significato

per ogni numero H=a*b dove (b-a) mod 8 == 0

 H,a ed b sono numeri dispari

 

non potresti scrivere il testo in un altro linguaggio? sembra che stai utilizzando istruzioni di un linguaggio di programmazione

@giandomenico si hai ragione non è scritto tanto bene

Un consiglio non cercare di capire tutto (sono 6 anni di studio)

concentrati sull'ultimo commento dato ad @artemsavka96

 

0

Vedo che stai utilizzando un metodo. Sei in MATLAB? 

@vi94 no 

 

Ok. Dato che la tua domanda non è da valutare in un calcolatore , dato i termini che hai postato, attraverso i connettivi logici, potresti mandare la traccia del libro?

@vi94 non c'è [credo] nessun libro che parla di queste cose.

però si potrebbe trovare la soluzione con un computer, analizzando gli output

 

0

Se ho capito bene, ho provato a risolverlo in generale, prova a dare un'occhiata alle foto e se non va bene qualcosa ci riprovo, segui il mio ragionamento, sono dalla 14 alla 1 a scendere

15854138218611388189794
15854137997001712353081
15854137738681446565899
1585413740222351250538
15854137084531435529944
15854136787951277580381
1585413637835815324564
15854136062811145943589
15854135569601577433653
1585413522202259415313
1585413498255421588146
1585413476470212440511
15854134125021546245575
1585413365988334865869

 

Questo è il generatore di tutti i numeri che soddisfano tali condizioni 

@artemsavka96 se ho ben capito quello che vuoi dire

in particolare generare è facile

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

basta dare i valori interi ad x ed y

Si, poi in base a x, ti trovi i valori di p e q, poi in base ai vari c che fissi ti trovi anche la d

 

@artemsavka96 non serve perchè il problema è trovare p e q 

Nella foto 12, mostra che p e q sono legate al variare di x, teoricamente x genera diversi valori di p e q

Domani cerco di scrivere il programma, così da poter avere qualche output per vedere se va bene

@artemsavka96 non teoricamente, è così

Quindi siamo sulla via giusta 

@artemsavka96 ti spiego l'idea di fondo

se abbiamo un numero di 8 cifre conosciuto e sappiamo che p è di 4 cifre allora conoscendo il rapporto tra gli ordini di c e d nei confronti di p ed N e tra di loro tramite un piccolo bruteforce possiamo risalire a p e quindi a q

Quindi vediamo se ho capito bene, 

Dato N di n cifre, sappiamo che p è composto da n-k cifre, 

Ora dobbiamo trovare i c e d, e vedere il rapporto che hanno con p e N

Giusto? 

@artemsavka96 si questa è l'analisi che devi fare, per poi fare il ragionamento inverso

Ho fatto il programma e ho fatto la prova per N=1000 e non ho ottenuto nessun risultato, ora sto provando su N più grandi, se vuoi ti posso passare il programma, è scritto in Java, se ti può essere utile

ciao @artemsavka96 devi testare gli N tali che p+q =4 mod 8 con p e q dispari

Ok, sto facendo anche delle modifiche per capire l'andamento di p e q, quella è una delle condizioni che ho imposto

@artemsavka96

gli N da testare sono gli N=H/3
esclusivamente di questa
(H-1)/8=3*x*(x+1)/2-3*y*(y-1)/2+(3*x+1)*(3*x+2)/2
e
p=[2*(3*x+1-(x-y+1))+1-(4*y-2)]
e
q=[2*(3*x+1-(x-y+1))+1]

Basandomi su questo esempio che hai inserito :

Ho fatto assumere a x ed y valori da 0 a 1000000 e al momento nessun valore di p e q è in grado di soddisfare le seguenti proprietà:

P*q (mod 8) == 0

(p+q-4) (mod 8) == 0

E la condizione di essere congrui

Se hai qualche altro consiglio da darmi 

@artemsavka96 P*q (mod 8) == 0 questa non deve essere verificata

Ok, mo ci riprovo e ti aggiorno 

Su 1000000*1000000 iterazioni per ogni valore di x e y, dopo 2 ore circa non aveva terminato, ho terminato il programma, riprovo su valori più bassi come 100000*100000,vedo se mi da qualche valore, se no lo lascio stanotte a fare 1000000*1000000, e domani ti aggiorno, se per te va bene 

@artemsavka96 ok 

solo per l'impegno messo ti darei il premio 

Hahaha ormai è diventata un'ossessione.

Eseguendo il programma ho notato che

Chiamo per semplicità 

Left = (H-1)/8

Right la parte di destra dell'espressione 

Dalle varie stampe di left e right, ho notato che non sono mai uguali per ogni valore di p*q e i vari valori assunti da x e y

Ora il mio dubbio è 

Va bene che pongo left==right

Quindi a te serve una chiave diretta e una inversa, giusto? 

 +10

Iscriviti su SosMatematica.it e ricevi 10 gemme oggi stesso.

+10

Iscriviti su SosMatematica.it e ricevi 10 gemme oggi stesso.