Forum de mathématiques - Bibm@th.net

Mac

Invité

Cryptographie, algèbre et crible quadratique

Bonjour à tous,

J'ai un projet qui porte sur la cryptographie et dans le but de factoriser des nombres premiers, j'ai implémenté la méthode du crible quadratique en python seulement j'ai encore quelques questions.

Tout d'abord j'aimerais savoir comment trouver, en python, le noyau d'une matrice de taille quelconque dont les coefficients sont uniquement 1 et 0.
A noter que je travail dans Z/2Z, donc ici 1+1=0.

Ensuite, pour le crible quadratique, le problème est qu'après ma phase de criblage, il me manque énormément de relation pour effectuer ma phase d'algèbre linéaire.

Je m'explique : je possède une liste1 = [1, 2, 3, 4, ... , T] et une liste2 = [1, 1, 1,  ... , 1] de même taille.
Après avoir criblé toute mes valeurs de la liste2 par ma base de facteur F = [2, 3, 5, 7, ..., B] de premiers B-friable, j'extrais les valeurs tel que f (liste1(i)) = liste2(i). Ces valeurs sont appelé relations et sont nécessaire pour la suite seulement je ne possède pas assez de relation pour continuer.

Ces notions peuvent paraitre étrange et mon explication un peu légère  mais j'ose espérer que ceux connaissant le crible quadratique m'ont compris.

Si quelqu'un pourrai m'éclairer a ce sujet car j'ai peut être mal compris comment fonctionnait le crible quadratique, un grand merci d'avance.

LCTD

Membre

Inscription : 21-11-2019

Messages : 101

Re : Cryptographie, algèbre et crible quadratique

Bonjour,

Vous dites de tailles quelconque :
1) si taille petite , inférieure à 5 alors utiliser la méthode de Gauss pour obtenir une matrice triangulaire
2) sinon, il faut utiliser les méthodes de matrices creuses ; chaque colonne a quelques entrées 1, simplifier son écriture creuse, pour réduire le nombre de lignes et de colonnes.

Dernière modification par LCTD (23-05-2022 21:22:47)