une ou deux petite qt

2 réponses

remy

21/10/2003 à 12:56

bonjour

juste pour le sport
une petite methode qui doit surement exister deja
trop simple

le but du jeu estime p avec p<q

m=p*q
a=sqrt(m)

r0=m%a
r1=(m+r0)%a
r2=(m+r0+r1)%a
...

l'on continue tant que r x diminue ou augmente

a l'arrivee
p est en gros egal a r0-((r0+r1+r2+...)%a)
la question combien de division modulo
quelle est la valeur de la difference entre l'estimation de p
et la valeur reelle de p

merci a +remy

2 réponses

Alain D.

21/10/2003 à 13:14

"remy" wrote in message
news:

a l'arrivee
p est en gros egal a r0-((r0+r1+r2+...)%a)
D'où tu tires ca?

Si je prends m*17"1, j'ai r0. Alors le p-XXX en gros, je suis pas
sur que ce soit vrai...
Alain

remy

21/10/2003 à 16:32

"remy" wrote in message
news:
a l'arrivee
p est en gros egal a r0-((r0+r1+r2+...)%a)
D'où tu tires ca?

Si je prends m*17"1, j'ai r0. Alors le p-XXX en gros, je suis pas
sur que ce soit vrai...
Alain

p<<q
m=2^1024

a=sqrt(m)
a=x*p+R
avec R trop grand pour une attaque par force brute

m%a=r0 r0=x0*p+r'

(m+r0)%a=r1 r1<r0 r1=x1*p+r''
(m+r0+r1)%a=r2 r2<r1 r2=x2*p+r'''
(m+r0+r1+r2)%a =r3 r3>r2

(x*p+R)-(x0*p+r'+x1*p+r''+x2*p+r''')%a

(x*p+R)-(xt*p+rt)

(x*p+xt)*p+(R-rt)

en gros je pense que cela reduit la taille de r
le but du jeu trouve un Xp

pb il faut que rt soit plus petit que R
je ne pense pas que cela soit toujours vrai

a+ remy

une ou deux petite qt

2 réponses

Veuillez sélectionner un problème