Ponieważ mnożenie liczb zapisanych w systemie liczbowym o danej podstawie jest w pewnym sensie splotem funkcji (cyfra jako wartość w funkcji potęgi podstawy), a transformata Fouriera splotu dwóch funkcji jest iloczynem ich transformat, zatem wielkie liczby naturalne można mnożyć szybko przez siebie, robiąc szybką transformatę Fouriera z ich cyfr, a następnie szybką transformatę odwrotną iloczynu tych transformat.
Implementacje Kod w Mathematica Krótki kod w języku Mathematica (tutaj sprawdzający liczbę pierwszą Mersenne’a Davida Slowinskiego & Paula Gage’a z 4 stycznia, 1994 (znaną 33.) z wykładnikiem ) w czasie nieco ponad 2 godzin na komputerze osobistym z procesorem Skylake o częstotliwości 2,9 GHz): Funkcja Mod[s, M] zwraca na końcu 0 jedynie jeśli jest liczbą pierwszą. M = 2^859433 - 1; s = 4; AbsoluteTiming[ Monitor[Do[ s = Mod[s*s - 2, M], {n, 1, 859433 - 2}], {ProgressIndicator[ n, {1, 859433 - 2}], n}]]; Print[Mod[s, M]]
Kod w Python Przykładowy kod w języku Python 3 wykorzystujący bibliotekę gmpy2, kod zawiera optymalizację dzielenia modulo (patrz wyżej – Złożoność czasowa) oraz monitorowanie pozostałego czasu wykonania (estymowanego).''' Dla liczby p > 2, funkcja zwraca True jeżeli 2^p-1 jest pierwsza, w innym razie zwraca False ''' from gmpy2 import * from datetime import *