判断对于给出的 m = p q ( p i s p r i m e ) , ( x , m ) = 1 , ( y , m ) = 1 m=p^q(p \ is \ prime),(x,m)=1,(y,m)=1 m=pq(p is prime),(x,m)=1,(y,m)=1， 是否存在 x a ≡ y ( m o d m ) x^a \equiv y \pmod m xa≡y(modm)
算 x x x和 y y y的阶 f ( ) f() f()： x a ≡ 1 ( m o d m ) , f ( x ) = min a x^a \equiv 1 \pmod m,f(x) = \min{a} xa≡1(modm),f(x)=mina 那么如果 f ( y ) ∣ f ( x ) f(y)|f(x) f(y)∣f(x)则有解。
求阶用试除法可以在 O ( log 2 ) O(\log^2) O(log2)的时间内计算。
