Jak znaleźć naturalne potęgi x oraz y, takie, że otrzymamy najmniejszą możliwą (nieujemną) różnicę wyrażenia:
\(\displaystyle{ 2^{x+y}-w^{x}}\)
podzielną przez liczbę naturalną p. Przy czym w to dowolna liczba naturalna równa lub większa niż 1.
W szczególnym przypadku, gdy \(\displaystyle{ w=1}\) musimy znaleźć najmniejszą potęgę \(\displaystyle{ 2^{n}-1}\), taką, że \(\displaystyle{ p}\) dzieli tę liczbę bez reszty. W tym wypadku, chyba najlepszym znanym algorytmem znajdowania takiej potęgi \(\displaystyle{ n}\) jest redukcja Pohliga-Hellmana (która najlepiej sprawdzi się dla gładkich \(\displaystyle{ p}\)).
Pomijając jednak ten szczególny przypadek. Co z przypadkami \(\displaystyle{ w>1}\). Czy dla każdego p zawsze istnieje \(\displaystyle{ 2^{x+y}-w^{x}}\) podzielne przez p? Czy znajdowanie takich potęg to problem logarytmiczny? Jak w najszybszym czasie znajdować rozwiązania tego problemu?