Factorisation des grands nombres

[nodgim]

Bonjour à tous.
Soit un nombre semi premier de 200 chiffres. Peut on en un seul test éliminer 10^50 nombres parmi les possibles facteurs ?

[Doraki]

Les possibles facteurs c'est tous les nombres premiers < racine( n) ?

[Ben314]

De plus, il me semble qu'il faudrait préciser ce que "un seul test" signifie.

Exemple :
Je me fixe une liste de premiers p1,p2,...pk plus petits que sqrt(n) et, pour chaque i je calcule le reste ri de la division de n par pi.
Je fait ensuite le produit R des ri.
Mon unique test est : R est il nul ?
Si la réponse est NON, j'ai éliminé k diviseurs potentiels de n (avec k égal à... ce que je veux)

Bon, a mon avis, c'est évidement pas ça la réponse attendue, mais de savoir pourquoi c'est pas ça... risque de m'éclairer sur la question...

P.S. : Posé comme ça, l'énoncé me fait un peut penser au "fameux" polynôme en je sais plus combien de variables qui, quand on regarde les valeurs positives qu'il prend sur les n-uplets d'entiers donne exactement la liste des nombres premiers.
Si on ne connait rien au domaine, la première fois que l'on voit le polynôme,... on est un peu décu...

[nodgim]

Non Ben, la métode employée ne fait pas intervenir les nombres premiers. Elle n'est pas monstrueuse et n'implique que peu de calculs.

[nodgim]

Les possibles facteurs c'est tous les nombres premiers < racine( n) ?

Plus précisément, en un seul test, on peut éliminer 10^50 nombres entiers consécutifs. Ce test peut être appliqué plusieurs fois, et à chaque fois on élimine 10^50 nombres consécutifs.

[Doraki]

tu veux dire des nombres premiers consécutifs ?

[nodgim]

Non, je dis bien des nombres entiers consécutifs.

[LeJeu]

Les possibles facteurs c'est tous les nombres premiers < racine( n) ?

Je te comprends bien Doraki, il faudrait tester les diviseurs de de 1 à racine(n) ( eurathosthènement parlant) pour trouver le(s) diviseur de n.

Mais ce n'est pas tout à fait le point de vue de Nodgim :il cherche à éliminer des candidats : pas à trouver la factorisation !

Je m'explique :considérons un nombre semi premier <= 10^4 (10 000) tu dis qu'il suffit de tester les diviseurs de 1 à 100 ( 10^2) , Nodgim dit qu'il peut éliminer 10 valeurs avec un seul test !

J'ai l'impression qu'il va éliminer des valeurs entre racine(n) et n ( entre 100 et 10 000 dans mon exemple)

Qu'en dis tu ?

[LeJeu]

je le vois de mieux en mieux:

On teste un truc entre 1 et racine (n) ( une divisibilité) et on ramasse la mise entre racine (n) et n.

j'adore : l'anti - crible : comment merder le plus possible !

en rédigeant ca doit le faire ?

[LeJeu]

Plus précisément, en un seul test, on peut éliminer 10^50 nombres entiers consécutifs. Ce test peut être appliqué plusieurs fois, et à chaque fois on élimine 10^50 nombres consécutifs.

On est d'accord sauf si on tombe 'par chance / malchance' sur le diviseur ( entre 1 et racine(n))

[LeJeu]

j'essaie de rédiger..

En testant ( la divisibilité d') un nombre entre 1 et racine (n) on élimine ( en moyenne ) [n-racine(n)] / [racine ( n) ] nombre ?

Edit :
dans mon exemple '10000' en élimine 100 valeur en moyenne...

En testant la divisibilité de n par x avec x compris entre 1 et racine(n) on élimine les nombres compris entre n / ( x+1) et n / ( x-1)

[edit]
à partir de là j'ai vraiment faux - j'efface - je continue dans mon prochain post

[nodgim]

On est d'accord sauf si on tombe 'par chance / malchance' sur le diviseur ( entre 1 et racine(n))

Bien sûr, le test vise directement la divisibilité du nombre. Si le test aboutit à une division sans reste, on a trouvé un diviseur. On sait que c'est le seul dans l'intervalle choisi. Sinon, il n'y a aucun diviseur dans cet intervalle.

[nodgim]

Je donne un indice: utiliser la courbe y=P/x avec P qui est le produit à factoriser. Il faut se servir du fait que, par la taille des nombres en jeu, la tangente de la courbe varie très lentement. Les décimales, après la virgule, de P/[racP] sont également très utiles.

[nodgim]

Je donne la réponse avant de perdre mes notes....

Comme la tangente à la courbe y=P/x vaut -1 quand x=racP, c'est intéressant de poser:
Si [VP] est la partie entière de la racine carrée de P, on cherche a tel que:
P/[VP]-P/([VP]+a)=a-1
et on arrive à ce résultat: a=V(VP).
Donc entre x=[P] et x=[P]+a, y n'a frolé qu'une fois une valeur entière au moment où x prend aussi une valeur entière. S'il y a une solution, elle ne peut être qu'unique.

Pour trouver cette éventuelle solution:
On pose R=partie décimale de la division P/[VP]. On cherche alors x tel que:
P/[VP]-P/([VP]+x)=x-(1-R)
Et on trouve cette bonne approximation:
x=V(1-R)*V(VP)

On peut sauter alors de cette approximation à la suivante et éliminer ainsi beaucoup de nombres, bien plus rapidement que s'il fallait tester les nombres premiers.
ça marche aussi lorsque la tangente prend des valeurs rationnelles simples, telles -9/10, -99/100, etc mais il faut prendre certaines précautions, et le saut est forcément plus petit. Pour les tangentes -1/2, -1/3, ...on retrouve des sauts de longueur équivalente à -1, mais là encore il faut faire attention.

Maintenant, il faut relativiser la portée de cette méthode. Elle n'a aucun intérêt quand la tangente à la courbe prend des valeurs différentes de celles indiquées ci-dessus. Tout au plus permet elle de tester rapidement des valeurs bien définies du rapport entre les 2 facteurs du semi-premier; Ce qui, lorsque ces facteurs sont pris au hasard, n'arrive pas souvent.