Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire
Veuillez sélectionner un problème
Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
Lo
l'etat de l'art actuellement pour factoriser m=p*q avec p<q
il faut combien d'essais ?
Pour m3*13, la méthode bourrine est de tester m/i avec i variant de 2 à 11, soit 10 essais, ou p-1.
La méthode qui nécessite le moins d'essais est, je pense, de tester m/i avec i variant de 2 à 11 ET i premier, soit 2,3,5,7,11, donc en 5 essais.
Le nombre min d'essais est donc le nombre de nb premiers inférieurs à p. Ce nombre, noté psi (p) ou phi (p) (je ne sais plus), n'est pas explicitable (logique!). Cependant, on en connaît un équivalent : p/ln(p) (ln ou log, là aussi, je ne sais plus).
@+ Lo
l'etat de l'art actuellement
pour factoriser m=p*q avec p<q
il faut combien d'essais ?
Pour m3*13, la méthode bourrine est de tester m/i avec i variant de 2
à 11, soit 10 essais, ou p-1.
La méthode qui nécessite le moins d'essais est, je pense, de tester m/i avec
i variant de 2 à 11 ET i premier, soit 2,3,5,7,11, donc en 5 essais.
Le nombre min d'essais est donc le nombre de nb premiers inférieurs à p. Ce
nombre, noté psi (p) ou phi (p) (je ne sais plus), n'est pas explicitable
(logique!). Cependant, on en connaît un équivalent : p/ln(p) (ln ou log, là
aussi, je ne sais plus).
l'etat de l'art actuellement pour factoriser m=p*q avec p<q
il faut combien d'essais ?
Pour m3*13, la méthode bourrine est de tester m/i avec i variant de 2 à 11, soit 10 essais, ou p-1.
La méthode qui nécessite le moins d'essais est, je pense, de tester m/i avec i variant de 2 à 11 ET i premier, soit 2,3,5,7,11, donc en 5 essais.
Le nombre min d'essais est donc le nombre de nb premiers inférieurs à p. Ce nombre, noté psi (p) ou phi (p) (je ne sais plus), n'est pas explicitable (logique!). Cependant, on en connaît un équivalent : p/ln(p) (ln ou log, là aussi, je ne sais plus).
@+ Lo
Jacques Caron
Salut,
On Mon, 01 Dec 2003 15:24:32 +0000, remy wrote:
l'etat de l'art actuellement pour factoriser m=p*q avec p<q
il faut combien d'essais ?
a priorie le nb d'essais doit etre inferieur a p si oui en gros p/2,p/3,p/?
Au minimum tu peux diviser par deux, p et q étant premiers, p ne peut être un multiple de deux :-) Et comme il ne peut pas être un multiple d'aucun autre nombre, ça diminue pas mal...
Jacques. -- Interactive Media Factory Création, développement et hébergement de services interactifs: SMS, SMS+, Audiotel... http://www.imfeurope.com/
Salut,
On Mon, 01 Dec 2003 15:24:32 +0000, remy <remy.aumeunier@libertysurf.fr>
wrote:
l'etat de l'art actuellement
pour factoriser m=p*q avec p<q
il faut combien d'essais ?
a priorie le nb d'essais doit etre inferieur a p
si oui en gros p/2,p/3,p/?
Au minimum tu peux diviser par deux, p et q étant premiers, p ne peut être
un multiple de deux :-) Et comme il ne peut pas être un multiple d'aucun
autre nombre, ça diminue pas mal...
Jacques.
--
Interactive Media Factory
Création, développement et hébergement
de services interactifs: SMS, SMS+, Audiotel...
http://www.imfeurope.com/
l'etat de l'art actuellement pour factoriser m=p*q avec p<q
il faut combien d'essais ?
a priorie le nb d'essais doit etre inferieur a p si oui en gros p/2,p/3,p/?
Au minimum tu peux diviser par deux, p et q étant premiers, p ne peut être un multiple de deux :-) Et comme il ne peut pas être un multiple d'aucun autre nombre, ça diminue pas mal...
Jacques. -- Interactive Media Factory Création, développement et hébergement de services interactifs: SMS, SMS+, Audiotel... http://www.imfeurope.com/
remy
l'etat de l'art actuellement pour factoriser m=p*q avec p<q
il faut combien d'essais ?
Pour m3*13, la méthode bourrine est de tester m/i avec i variant de 2 à 11, soit 10 essais, ou p-1.
La méthode qui nécessite le moins d'essais est, je pense, de tester m/i avec i variant de 2 à 11 ET i premier, soit 2,3,5,7,11, donc en 5 essais.
Le nombre min d'essais est donc le nombre de nb premiers inférieurs à p. Ce nombre, noté psi (p) ou phi (p) (je ne sais plus), n'est pas explicitable (logique!). Cependant, on en connaît un équivalent : p/ln(p) (ln ou log, là aussi, je ne sais plus). merci
la question posee differemment
m=p*q m et d'une taille de 2^1024
p et d'une taille de 2^256 q et d'une taille de 2^768
le meilleur algo de factorisation actuelle trouve p et q en gros en 2^256/x essai
@+ Lo
l'etat de l'art actuellement
pour factoriser m=p*q avec p<q
il faut combien d'essais ?
Pour m3*13, la méthode bourrine est de tester m/i avec i variant de 2
à 11, soit 10 essais, ou p-1.
La méthode qui nécessite le moins d'essais est, je pense, de tester m/i avec
i variant de 2 à 11 ET i premier, soit 2,3,5,7,11, donc en 5 essais.
Le nombre min d'essais est donc le nombre de nb premiers inférieurs à p. Ce
nombre, noté psi (p) ou phi (p) (je ne sais plus), n'est pas explicitable
(logique!). Cependant, on en connaît un équivalent : p/ln(p) (ln ou log, là
aussi, je ne sais plus).
merci
la question posee differemment
m=p*q
m et d'une taille de 2^1024
p et d'une taille de 2^256
q et d'une taille de 2^768
le meilleur algo de factorisation actuelle trouve
p et q en gros en 2^256/x essai
l'etat de l'art actuellement pour factoriser m=p*q avec p<q
il faut combien d'essais ?
Pour m3*13, la méthode bourrine est de tester m/i avec i variant de 2 à 11, soit 10 essais, ou p-1.
La méthode qui nécessite le moins d'essais est, je pense, de tester m/i avec i variant de 2 à 11 ET i premier, soit 2,3,5,7,11, donc en 5 essais.
Le nombre min d'essais est donc le nombre de nb premiers inférieurs à p. Ce nombre, noté psi (p) ou phi (p) (je ne sais plus), n'est pas explicitable (logique!). Cependant, on en connaît un équivalent : p/ln(p) (ln ou log, là aussi, je ne sais plus). merci
la question posee differemment
m=p*q m et d'une taille de 2^1024
p et d'une taille de 2^256 q et d'une taille de 2^768
le meilleur algo de factorisation actuelle trouve p et q en gros en 2^256/x essai
@+ Lo
Lo
la question posee differemment
m=p*q m et d'une taille de 2^1024
p et d'une taille de 2^256 q et d'une taille de 2^768
le meilleur algo de factorisation actuelle trouve p et q en gros en 2^256/x essai
Oui, donc, je disais qu'il faut p/ln(p), donc x=ln(p).
Ce n'est pas une égalité en fait, c'est une équivalence lorsque p est assez grand. Pour p=2^256, une bonne approximation doit être p/256 essais.
la question posee differemment
m=p*q
m et d'une taille de 2^1024
p et d'une taille de 2^256
q et d'une taille de 2^768
le meilleur algo de factorisation actuelle trouve
p et q en gros en 2^256/x essai
Oui, donc, je disais qu'il faut p/ln(p), donc x=ln(p).
Ce n'est pas une égalité en fait, c'est une équivalence lorsque p est assez
grand.
Pour p=2^256, une bonne approximation doit être p/256 essais.
p et d'une taille de 2^256 q et d'une taille de 2^768
le meilleur algo de factorisation actuelle trouve p et q en gros en 2^256/x essai
Oui, donc, je disais qu'il faut p/ln(p), donc x=ln(p).
Ce n'est pas une égalité en fait, c'est une équivalence lorsque p est assez grand. Pour p=2^256, une bonne approximation doit être p/256 essais.
Klopfenstein Michaël
Votre question sans le vouloir est mal posée, elle génère un quiproquo. En effet, il n'existe pas de coefficients x tel que la factorisation de n=pq soit fait en n/x essais.
**** Méthode élémentaire de factorisation **** - Si le nombre 'n' se factorise, il existe un nombre premier p tel que n=p.r donc la factorisation se fait en testant les nombres premiers un à un en démarant avec le nombre 2,3,5,7,11,13,etc... - deuxième remarque : il est inutile de testé jusqu'à n, si aucun n'a fonctionné jusqu' racine(n), c'est que le nombre est premier. - troisième remarque : sachant que la quantité de nombre premier avant n est environ égale à n/ln(n), on peut estimer combien de test il faudra faire au maximum Le nombre maximum est environ égale à 2.racine(n)/ln(n) On voit ici que le coefficient x que vous demandiez dépend de n, il n'est pas fixe (autrement dit le nombre de calcul à effectué n'est pas 'linéaire')
**** Méthode avancé de factorisation **** Mais il s'agit ici d'un méthode élémentaire. Les programmes de calcul qui factorise les grands nombres utilisent des méthodes extrêmement plus complexe. Les nombres premiers 'se rangent en catégories' qui vérifie des propriétés particulières, on effectue alors des tests sur le nombre n, qui permette de prévoir la méthode de factorisation. Dans l'écrasante majorité des cas, il existe un test qui fonctionne et qui permet d'accélerer la factorisation. On peut donc difficilement parler de la rapidité de factorisation dans le cas général : car chaque nombre n possède des propriétés particulières. On parle souvent en probabilité : un nombre n possède 97 chances sur 100 d'être factorisé en tant de test. Les mathématiques utilisés dans ces méthodes sont issue de la théorie des nombres, et le meilleures méthodes sont sans cesse affinées par quelques grand experts mondiaux, elles sont inaccessibles au non professionnel, elle repose sur des théories élaborées. Je connais quelques test de bases, mais je suis incapable de vous donner les formules probabiliste donnant les vitesses de factorisation standard des meilleures méthodes actuelles.
MK
Votre question sans le vouloir est mal posée, elle génère un quiproquo.
En effet, il n'existe pas de coefficients x tel que la factorisation de n=pq
soit fait en n/x essais.
**** Méthode élémentaire de factorisation ****
- Si le nombre 'n' se factorise, il existe un nombre premier p tel que n=p.r
donc la factorisation se fait en testant les nombres premiers un à un en
démarant avec le nombre
2,3,5,7,11,13,etc...
- deuxième remarque : il est inutile de testé jusqu'à n, si aucun n'a
fonctionné jusqu' racine(n), c'est que le nombre est premier.
- troisième remarque : sachant que la quantité de nombre premier avant n est
environ égale à n/ln(n), on peut estimer combien de test il faudra faire au
maximum
Le nombre maximum est environ égale à 2.racine(n)/ln(n)
On voit ici que le coefficient x que vous demandiez dépend de n, il n'est
pas fixe (autrement dit le nombre de calcul à effectué n'est pas 'linéaire')
**** Méthode avancé de factorisation ****
Mais il s'agit ici d'un méthode élémentaire. Les programmes de calcul qui
factorise les grands nombres utilisent des méthodes extrêmement plus
complexe.
Les nombres premiers 'se rangent en catégories' qui vérifie des propriétés
particulières, on effectue alors des tests sur le nombre n, qui permette de
prévoir la méthode de factorisation.
Dans l'écrasante majorité des cas, il existe un test qui fonctionne et qui
permet d'accélerer la factorisation.
On peut donc difficilement parler de la rapidité de factorisation dans le
cas général : car chaque nombre n possède des propriétés particulières. On
parle souvent en probabilité : un nombre n possède 97 chances sur 100 d'être
factorisé en tant de test.
Les mathématiques utilisés dans ces méthodes sont issue de la théorie des
nombres, et le meilleures méthodes sont sans cesse affinées par quelques
grand experts mondiaux, elles sont inaccessibles au non professionnel, elle
repose sur des théories élaborées.
Je connais quelques test de bases, mais je suis incapable de vous donner les
formules probabiliste donnant les vitesses de factorisation standard des
meilleures méthodes actuelles.
Votre question sans le vouloir est mal posée, elle génère un quiproquo. En effet, il n'existe pas de coefficients x tel que la factorisation de n=pq soit fait en n/x essais.
**** Méthode élémentaire de factorisation **** - Si le nombre 'n' se factorise, il existe un nombre premier p tel que n=p.r donc la factorisation se fait en testant les nombres premiers un à un en démarant avec le nombre 2,3,5,7,11,13,etc... - deuxième remarque : il est inutile de testé jusqu'à n, si aucun n'a fonctionné jusqu' racine(n), c'est que le nombre est premier. - troisième remarque : sachant que la quantité de nombre premier avant n est environ égale à n/ln(n), on peut estimer combien de test il faudra faire au maximum Le nombre maximum est environ égale à 2.racine(n)/ln(n) On voit ici que le coefficient x que vous demandiez dépend de n, il n'est pas fixe (autrement dit le nombre de calcul à effectué n'est pas 'linéaire')
**** Méthode avancé de factorisation **** Mais il s'agit ici d'un méthode élémentaire. Les programmes de calcul qui factorise les grands nombres utilisent des méthodes extrêmement plus complexe. Les nombres premiers 'se rangent en catégories' qui vérifie des propriétés particulières, on effectue alors des tests sur le nombre n, qui permette de prévoir la méthode de factorisation. Dans l'écrasante majorité des cas, il existe un test qui fonctionne et qui permet d'accélerer la factorisation. On peut donc difficilement parler de la rapidité de factorisation dans le cas général : car chaque nombre n possède des propriétés particulières. On parle souvent en probabilité : un nombre n possède 97 chances sur 100 d'être factorisé en tant de test. Les mathématiques utilisés dans ces méthodes sont issue de la théorie des nombres, et le meilleures méthodes sont sans cesse affinées par quelques grand experts mondiaux, elles sont inaccessibles au non professionnel, elle repose sur des théories élaborées. Je connais quelques test de bases, mais je suis incapable de vous donner les formules probabiliste donnant les vitesses de factorisation standard des meilleures méthodes actuelles.
MK
remy
On Mon, 01 Dec 2003 19:16:48 +0100, Lo wrote:
la question posee differemment
m=p*q m et d'une taille de 2^1024
p et d'une taille de 2^256 q et d'une taille de 2^768
le meilleur algo de factorisation actuelle trouve p et q en gros en 2^256/x essai
Oui, donc, je disais qu'il faut p/ln(p), donc x=ln(p).
Ce n'est pas une égalité en fait, c'est une équivalence lorsque p est assez grand. Pour p=2^256, une bonne approximation doit être p/256 essais.
ok tu me dit que le meilleur algo pour factorise p ses de prendre tout les nb premmier entre 1 et p se qui egale a phi(p) et en gros p/(ln(p))
je suis d'accord
mais qt je dit "le meilleur algo de factorisation actuelle " je ne sais pas calcul toute les nb premmier entre 1 et p
et si je dois les calculer cela revient a faire m/i avec i=1...p donc p essai
On Mon, 01 Dec 2003 19:16:48 +0100, Lo wrote:
la question posee differemment
m=p*q
m et d'une taille de 2^1024
p et d'une taille de 2^256
q et d'une taille de 2^768
le meilleur algo de factorisation actuelle trouve p et q en gros en
2^256/x essai
Oui, donc, je disais qu'il faut p/ln(p), donc x=ln(p).
Ce n'est pas une égalité en fait, c'est une équivalence lorsque p est
assez grand.
Pour p=2^256, une bonne approximation doit être p/256 essais.
ok tu me dit que le meilleur algo pour factorise p
ses de prendre tout les nb premmier entre 1 et p
se qui egale a phi(p) et en gros p/(ln(p))
je suis d'accord
mais qt je dit
"le meilleur algo de factorisation actuelle "
je ne sais pas calcul toute les nb premmier
entre 1 et p
et si je dois les calculer cela revient a
faire m/i avec i=1...p donc p essai
