Coppersmith-methode
De Coppersmith methode is een factorisatie methode, voornamelijk toegepast in cryptografie. Don Coppersmith heeft verschillende bijdragen aan de cryptografie geleverd, waaronder twee stellingen in 1996 en 1997.

Inleiding 
Factoriseren bij kleine getallen is vrij eenvoudig te doen door van alle priemgetallen, kleiner dan de wortel van het te factoriseren getal, te controleren of het erdoor is te delen, bijvoorbeeld: . Dat wordt meer werk als de getallen groter worden.

In de cryptografie is het vaak nodig om modulair rekenen te gebruiken, rekenen modulo een getal N.

De Coppersmith methode is een manier om nulpunten te vinden van een polynoom modulo een getal  met p en q beide priem. Daarbij is het de bedoeling om een klein nulpunt  van de polynoom te vinden. Daarmee wordt bedoeld dat het getal .

De idee achter de methode 
Met de methode van Coppersmith willen we een wortel  van een polynoom  van graad n vinden modulo N. De polynoom schrijven we als  modulo N, met . De wortel die we zoeken moet een geheel getal zijn, maar de polynoom is gedefinieerd over ring . We willen de polynoom daarom herschrijven zodat we  vinden als nulpunt van een polynoom h(x), zonder daarbij rekening te houden met modulo rekening. Daarom kiezen we een bovengrens voor . Vervolgens zullen we daadwerkelijk de polynoom herschrijven.

Om de voornoemde polynoom h(x) te construeren kiezen we een getal m en vinden de set van polynomen  met k=0, 1, ..., m. Merk op dat als  een wortel is van F(x), dan is dat getal ook wortel van  modulo .
Wanneer we nu h(x) kiezen als een lineaire combinatie met gehele coëfficiënten van verschillende polynomen , vinden we dat  een nulpunt modulo  van deze polynoom is.

Met de stelling van Howgrave-Graham kunnen we met zekerheid zeggen dat , tenminste als we kunnen aantonen dat  modulo  en  met  het aantal coëfficiënten ongelijk aan nul in .

Dus als we in staat zijn om h(x) zo te construeren dat hij aan de voorwaarden voldoet van de stelling van Howgrave-Graham, hoeven we slechts h(x)=0 op te lossen over de gehele getallen. Maar hoe precies vinden we een geschikte h(x). Een geschikte polynoom kunnen we vinden door het Gram-Schmidtmethode toe te passen op een bepaalde set , echter weten we dan niet zeker of de gereduceerde basis aan de voorwaarde  voldoet. Dat is de reden om het LLL-algoritme toe te passen, omdat we dan verzekerd zijn dat ||h(xX)|| klein genoeg is.

Vereenvoudigde methode 
Om een nulpunt  te vinden van een polynoom F(x) van graad n modulo N, schrijven we de uitdrukking F(x) als volgt op als een matrix:

 

Hierin is elke rij gelijk aan een polynoom met wortel  modulo .

Deze matrix vatten we op als een verzameling waarop we het LLL-algoritme toepassen. We vinden dan vectoren waarbij de eerste rij van de volgende vorm is:
.
Vat deze rij op als de uitdrukking h(X) en vervang hierin de X voor de variabele x.

De nulpuntvergelijking van de nieuwe polynoom h(x) kan worden opgelost met het Newton-Raphson-algoritme. Hierbij hoeft niet modulo N gerekend te worden, maar wel modulo . Maar omdat we vaststelden dat geldt voor de te vinden oplossing  dat , hoeven we hier geen rekening meer mee te houden.

De methode 
Om te zorgen dat met het LLL-algoritme een gereduceerde basis gevonden wordt, is het soms nodig om de matrix uit te breiden. Daarbij is de laatste rij een macht van de polynoom F en alle kleinere machten van F verschijnen met geschikte machten van N.

De nieuwe matrix ziet er bijvoorbeeld als volgt uit (laatste rij is ,):

 

de eerste vector van de LLL gereduceerde basis is nu van de vorm  Vervang hierin de X voor de variabele x en beschouw de uitdrukking als een polynoom h(x) van graad 2n. Wederom wordt met het Newton-Raphson-algoritme een nulpunt bepaald, zonder modulo N te hoeven rekenen.

Externe link 
  

Cryptografie