PureBasic

Bonsoir,
Comme je l’ai déjà dit, je suis cette discussion avec intérêt, même si mes « hobbies » me posent moins de problèmes de recherche de primalité que de problèmes de factorisation, ou de problèmes de recherche de combinaisons de fractions qui approchent le plus possible un nombre réel élevé, qu’il soit premier ou pas (problèmes aujourd’hui résolus).

Le test de primalité par les nombres de la forme 6a+b, ou encore plus de la forme 30a+b, permet de réduire de façon importante la durée du test par rapport à la « méthode naïve » de division par tous les nombres en partant de 2, les pairs étant quand même exclus.

Du fait de mes connaissances modestes en informatique je ne comprends pas pourquoi le multithreading pourrait apporter des gains de temps décoiffants.
Tchargal peut il nous expliquer ? Merci.

Il me semble que pendant un test de primalité, quelle que soit la méthode utilisée, le processeur tourne à 100% du temps sur le thread en cours, parce qu'il n’a pas de temps d’attente de réponse d’une ressource quelconque. Comment alors lui soumettre un autre thread à traiter alors qu’il est déjà « ras la gueule ».
Par contre, je comprends qu’en multiprocesseurs on puisse faire du parallélisme sur le même test de primalité, et réduire d’autant le temps d’exécution, en confiant à chaque processeur un groupe de diviseurs à essayer.

A l’époque où je ne les avais pas optimisés, quand je lançais mes algos itératifs de recherche de fractions, ils duraient plusieurs minutes et je constatais que le ventilateur du processeur démarrait de suite après le lancement, signe que le processeur chauffait parce qu’il tournait à fond, qu’il était sur le chemin critique de l’exécution de l’algorithme en cours, qu’il ne pouvait rien absorber d’autre.

Mais encore une fois, je dis peut être des énormités (pas taper ) par manque de compétences.

Comme vous le savez sans doute, nos processeurs sont en fait des multiprocesseurs depuis quelques années maintenant. (vous pouvez les observer dans le moniteur de ressource de Windows par exemple)

Le mien, par exemple, contient 8 cœurs, eux même contenant plusieurs pipelines structurés en parallèles.
Chaque cœur décompose les instructions dans les pipelines, indépendamment de notre volonté.

Néanmoins, on peut affecter une tache à chacun des 8 cœurs séparément et volontairement comme on le ferait sur un octo-processeurs "d'autrefois".

Oui, tout à fait et ils fonctionnent de la même manière qu'autrefois et maintenant encore, quand on connectait plusieurs ordinateurs qui fonctionnaient en mode "clipping", où chaque ordinateur calculait pour un autre, ce qui permettait d'avoir une plus grande précision de calcul et n'empêchait pas de travailler normalement pour faire d'autres tâches.

Bonjour,
Merci Fig et Micoute pour vos précisions.
Et merci aussi bien sûr à PAPIPP et Tchargal pour leur travail sur le test de primalité.

En prenant la phrase suivante trouvée sur Wiki en ce qui concerne les threads :

« Contrairement aux systèmes multiprocesseurs (tels les systèmes multi-cœur), les threads doivent partager les ressources d'un unique cœur : les unités de traitement, le cache processeur et le translation lookaside buffer ; certaines parties sont néanmoins dupliquées : chaque thread dispose de ses propres registres et de son propre pointeur d'instruction »,

je voulais dire qu’on ne devrait pas gagner de temps d’exécution sur un cœur du processeur donné, en voulant faire du multithreads sur lui, étant donné qu’un test de primalité fait travailler ce cœur à fond et ne lui laisse pas de temps libre pour prendre un autre thread.

Mais s’agissant de faire du parallélisme sur les différents cœurs du processeur pour un test de primalité, là c’est d’accord……à condition de savoir le faire,……ce que je ne sais pas,....encore.
Sur un portable je n’essaierais même pas, à cause du problème de l’échauffement. J’attendrais d’avoir un PC à refroidissement du processeur par liquide, genre circuit d’eau glycolée....et à matrice à couche de diamant
Mes algorithmes d'aujourd'hui, même les plus lourds, s’exécutent encore dans des temps courts sans dispositions particulières. Le jour où ils prendront du poids je vous demanderai de l’aide.

Bonsoir,
et merci à tous ces doctes participants !

Il me parait certain et évident que nous sommes bien loin de l’algorithme ultime en matière de primalité ! Certains ont déjà cassé du RSA ( https://fr.wikipedia.org/wiki/Chiffrement_RSA ) et la cryptographie de haut niveau doit avoir des outils de très haut niveau
Nos algo à base de 6n±1 ou de 30x + y doivent bien faire sourire la NSA !
Voilà bien des années que je fouille le net à la recherche d'algorithmes "costauds" ou de programmes sur la primalité, et bien il n'y a RIEN, que dalle, que t'chi, walou... Et pour cause, c'est la chasse gardée des banques, des gouvernements et autres institutions louches

Et pourtant, il doit bien y avoir quelques universités qui ont ça sous le coude, mais je ne pense pas qu'ils mettrons leurs programmes dans le domaine public... trop dangereux sachant que même vos codes de carte bleue sont basés sur les nombres premiers !

Bonsoir,

En effet :
- Ceux qui essaient de casser le cryptage RSA à des fins frauduleuses ne vont pas exposer leurs nouvelles approches sur Internet.
- Les états voyous, « s’il en existe », qui pour des raisons politiques veulent le casser aussi, ne vont pas non plus s’en vanter.
- Les universités si elles trouvent des failles dans le cryptage RSA vont d‘abord en parler à RSA avant de publier quoi que ce soit, pour des raisons d’éthique auxquelles elles sont tenues, et aussi pour plutôt obtenir des crédits de RSA pour financer leurs recherches et aider RSA à trouver de nouvelles parades.

De plus les attaques contre le cryptage RSA ne se font pas seulement par les algorithmes force brute sur la primalité, mais aussi par des astuces, comme celles décrites dans le lien que Tchargal a indiqué : « attaque par chronométrage », « attaque par chiffrement choisi », etc.
Les Allemands pendant la dernière guerre mondiale étaient loin de se douter que les Anglais cassaient le cryptage des messages de leur machine Enigma, déjà parce qu’ils en connaissaient le principe de cryptage, ensuite parce que Alan Turing avait mis au point les premiers computers, mais aussi tout bêtement parce que les opérateurs allemands terminaient toujours les messages qu’ils envoyaient par les deux lettres HH (qui voulaient dire Heil Hitler). Les Anglais commençaient donc par aller voir comment les Allemands cryptaient le H ….et une fois qu’on a une lettre le décryptage devient plus facile.

La RSA est sur ses gardes (et on l’en remercie pour nos cartes bancaires). Elle doit renforcer ses protections et prévoir d’allonger sa clé au fur et à mesure que la puissance de calcul progresse.

Il semble que la grande révolution dans ce domaine viendra de la deuxième révolution quantique, celle qui a commencé en 1964 quand John Bell a formulé ses fameuses inégalités, appelées depuis inégalités de Bell, qui tranchaient le vieux débat entre Einstein et Niels Bohr.
Mais c’est en 1982 qu’elle a vraiment eu lieu, quand le physicien français Alain Aspect et son équipe ont validé l’une des plus étonnantes propriétés de la matière : l’intrication quantique.

On peut acheter pour quelques Euros les conférences de l'Académie des Sciences et plus particulièrement celle de Alain Aspect sur ce sujet de l'intrication quantique. Il s'exprime dans un langage de vulgarisation accessible à tous. Il dit (à tort ou à raison, je ne suis pas à même d’en juger) que la révolution dans le cryptage des données viendra de l’intrication quantique :
Primo :
Parce que les ordinateurs quantiques permettront un parallélisme vraiment massif qui "cassera" les clés les plus longues.
Secundo :
Parce que le cryptage quantique sécurisera vraiment la transmission de données par le seul fait que si le message est écouté par un espion, l’émetteur et de destinataire s’en rendront obligatoirement compte immédiatement et qu’ils s’abstiendront de faire jouer les clés de cryptage, et donc éviteront de les dévoiler.
Il semblerait que le cryptage quantique soit déjà opérationnel et utilisé par de « grandes organisations ».

Si la RSA était déjà bien au-dessus de nos maigres capacités, là nous n’existerons même plus.

Très intéressant Surlen, on peut déjà voir et écouter le bonhomme ici : https://www.youtube.com/watch?v=dA7cPqn6NOY
Il parle du coup de Nicolas Gisin expert de la téléportation quantique et de la crypto quantique.
J'adore même si je ne pipe pas tout.

Bonjour,
Ar-S, je ne connaissais pas cette conférence de Alain Aspect et je vais la suivre avec attention.

Elle parait moins facile pour les non-initiés que celle, toujours de Alain Aspect, sous forme de simples fichiers audios, dont j’ai parlé précédemment et qui sont disponibles ici. Ce n’est pas gratuit mais elle vaut largement les quelques Euros de son prix
Je ne l’ai pas cherchée sur YouTube. Si on en achète en même temps plusieurs à DeViveVoix sur différents sujets, on obtient de meilleurs prix
https://www.devivevoix.com/livre-audio/ ... in-aspect/

Dans la série, celle sur la Théorie du Chaos ci-dessous vaut aussi son prix.
https://www.devivevoix.com/livre-audio/ ... enne-ghys/

Quand je trouverai un peu de temps je ferai tourner des algos qui génèrent des attracteurs de Lorentz.

Je viens de voir que les particules issues du rayonnement de Hawking n'étaient pas intriqués.

C'est quand même fou : une particule née de l'arrachement d'elle-même avec son anti-particule intriquée n'est, dans le cas du rayonnement de Hawking, pas intriquée.

Comme ce n'est "que" de la théorie, ça montre que les maths, ça avance sévèrement !