Osobną linią badań była metoda relacji w grupie klas, rozwijana przez Clausa P. Schnorra, Martina Seysena i Arjena K. Lenstrę. W pierwotnych analizach jej działanie wiązano z założeniami takimi jak uogólniona hipoteza Riemanna, a algorytm używa relacji w grupach klas dodatnio określonych binarnych form kwadratowych o odpowiednim wyróżniku.

Hendrik W. Lenstra i Carl Pomerance uzyskali później ścisłe oszacowanie oczekiwanego czasu dla wariantu tej metody bez odwoływania się do uogólnionej hipotezy Riemanna. Wynik ten pokazał, że można uzyskać rygorystyczny czas oczekiwany rzędu zastępując założenie hipotezy odpowiednim doborem mnożników.

Komputery kwantowe Algorytm Shora, opisany w 1994 roku i opublikowany w pełnej wersji w 1997 roku, rozwiązuje faktoryzację w czasie wielomianowym na komputerze kwantowym. Dla wejścia o długości bitów często podaje się czas rzędu i pamięć rzędu To zasadnicza różnica wobec najlepszych znanych metod klasycznych.

Pierwsze demonstracje algorytmu Shora rozkładały bardzo małe liczby i miały charakter eksperymentalny.