Discussion :

[Guesset]

Bonjour wiwaxia,

Merci pour ta réponse sur les signes mathématiques. J'espérais quelque chose de plus direct mais en les mettant eux seuls dans un fichier txt et en faisant de copier/coller, ça doit le faire.

...
Ce qui ne cesse de m'étonner, c'est la réponse quasi instantanée de WolframAlpha (et de quelques autres logiciels) à ce genre de problème:
factor | 12345678901234567890123456789012345678901234567890123456789012345678901234567890
Result:
2×3^2×5×17×73×101×137×3541×3607×3803×27961×1676321×5070721×5882353×5964848081×19721061166646717498359681 (17 prime factors, 16 distinct)

Il y a aujourd'hui des algo performants (courbes elliptiques, etc.) mais 80 chiffres ne représentent qu'environ 270 bits là où la crypto utilise 1000 ou 2000 bits voire plus si affinité. Par ailleurs, je parie que le parallélisme (voire le multi machine) est mis à contribution pour diviser les temps.

Salut

[laurent_ott]

Bonjour à vous tous.

Pour commencer je tiens à rectifier ce que j'ai écrit au message 38 : il ne semble pas possible de savoir si un nombre est semi-premier sans calculer au préalable ses facteurs.

Ensuite, je marque cette discussion comme résolue car vous avez apporté une réponse à ma demande initiale.

Quant à la vitesse de traitement des logiciels disponibles sur internet, qui factorisent 12345678901234567890123456789012345678901234567890123456789012345678901234567890 quasi immédiatement, j'ai aussi été très impressionné, et c'est pourquoi j'ai passé du temps à optimiser mes traitements. Avec les ressources dont je dispose (matériel et langage de programmation), il ressort que :
- la taille de la base des nombres premiers à tester doit rester faible (664 579 permettent de tester les nombres jusqu'à 10 000 000), car les essais sont chronophages ;
- au lieu de faire une division sur chacun de ces nombres il est plus rapide de ne tester que le modulo, puis faire la division si le reste vaut zéro. J'ai donc cogité pour cet algorithme, qui peut-être vous intéressera, (à savoir que la fonction MOD du VBA ne supporte pas un diviseur de plus de 9 chiffres) car dans mon cas j'ai toujours un "petit" diviseur et un "grand" dividende:

Code VBA :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
'---------------------------------------------------------------------------------------
Public Function ModGNDV(ByVal vcChiffre As String, Diviseur As Variant) As Variant
'---------------------------------------------------------------------------------------
While Len(vcChiffre) > 22
    vcChiffre = CStr(ModuloGN(Left(vcChiffre, 22), Diviseur)) & Mid(vcChiffre, 23)
Wend
ModGNDV = ModuloGN(vcChiffre, Diviseur)
End Function
 
'---------------------------------------------------------------------------------------
Private Function ModuloGN(vcChiffre As String, Diviseur As Variant) As Variant
'---------------------------------------------------------------------------------------
ModuloGN = vcChiffre - (CDec(Diviseur) * Fix(vcChiffre / CDec(Diviseur)))
End Function
'---------------------------------------------------------------------------------------

Au final : j'arrive à factoriser rapidement des nombres jusqu'à 28 caractères (les capacités numériques du VBA), et en temps "raisonnable" des nombres de moins de 45 caractères, au dessus c'est plus long, et à partir de 55 caractères les temps de traitement sont trop longs (il me faudrait plus de ressources mémoire pour le crible quadratique), sauf quand le nombre peut-être en partie factorisé par les premiers de ma base, comme le nombre vu plus haut, qui donne :
2*3*3*5*17*73*101*137*3541*3607*3803*27961*1676321*5070721*5882353
Ne reste plus qu'à trouver : 5964848081*19721061166646717498359681.

Pour finir, et dans un tout autre registre, je recherche des informations sur la méthode pour calculer un logarithme népérien avec une forte précision. Je m'explique :
en VBA log(341) = 5,83188247728352 soit une précision de 14 chiffres.
avec une simple calculatrice ln(341) = 5,8318824772835167899911079025075 soit une précision de 31 chiffres.
Savez-vous comment faire ?

Merci encore à vous tous pour votre implication.
Laurent Ott.

[tcorps]

tu ne pourras pas resoudre l'equation il te manque un element important ta cle de cryptation sinon dans ton alghorythme c'est le resultat avec un decale boeliens en realiter ta cle chiffrer aes mnt pour faire court tu recalcul ton boeenlien decalage tu reviens à ta cle de crypter de depart ici dans mon calcul ta cle sera 10a10b donc ton facteur n

[Guesset]

Bonjour Laurent,

... au lieu de faire une division sur chacun de ces nombres il est plus rapide de ne tester que le modulo, puis faire la division si le reste vaut zéro...

Navré de te décevoir mais pour un CPU, X64 entre autres, div et mod sont une seule et même opération DIV ou IDIV qui retourne à la fois le résultat de la division et le reste de celle-ci c'est à dire le modulo. C'est pourquoi on trouve souvent une instruction divmod qui habille le code assembleur d'une division et récupère le quotient et le reste. Si VBA t'offre cette possibilité tu n'as pas à hésiter.

D'un autre coté, même si ton approche ne fait rien gagner, elle n'est pas désastreuse car les quelque divisions économisées par divmod dépendent du nombre de facteurs qui, en crypto, se limite à 2.

Salut

[laurent_ott]

Navré de te décevoir mais pour un CPU, X64 entre autres, div et mod sont une seule et même opération DIV ou IDIV qui retourne à la fois le résultat de la division et le reste de celle-ci c'est à dire le modulo. C'est pourquoi on trouve souvent une instruction divmod qui habille le code assembleur d'une division et récupère le quotient et le reste. Si VBA t'offre cette possibilité tu n'as pas à hésiter.

Bonjour Guesset.
Malheureusement le VBA ne permet pas de traiter des numeriques de plus de 28 caractères. Pour des nombres plus grands il faut ''reprogrammer'' (en chaîne) les opérations de base : addition, soustraction, multiplication, division, modulo, etc (je vous laisse imaginer le boulot que ça représente. Cette programmation ne vient pas de moi, sauf la division, comme déjà indiqué). D'où des temps de traitement plus longs qu'avec des langages qui gèrent nativement les grands nombres. C'est pourquoi je recherche des raccourcis, qui ne concernent effectivement pas tous les langages de programmation : j'aurais dû le préciser.
J'aurais dû aussi préciser que je cherche à factoriser des entiers, pas forcément semi premiers, donc pas nécessairement un lien avec RSA.
Merci pour l'intérêt que vous portez à cette discussion.
Cordialement.