1、数论、组合数学、具体数学李 寅Euclidean algorithm Gcd( a , b ) = gcd( b*(a/b)+(a%b) , b ) = gcd( b , a%b ) = Extended Euclidean algorithmThe iterative methodThe recursive methodThe iterative method Recursive methodMiller Rabbin BASIS: ap mod p = aThat is , a(p-1) mod p = 1TOOLS: power_productCycle detectionRhoHow
2、to calculate : HASH?Floyds cycle-finding algorithm The key insight in the algorithm is that, whenever i 0 is a multiple of that is greater than , xi = x2i (and conversely). Thus, we need only check for repeated values of this special form to find a period of a repetition that is a multiple of . Once is found, we may retrace the sequence from its start to find the first repetition of length ; since divides , x + = x, the start of the first repetition. Finally, from x it is trivial to find the length of the shortest repeating cycle, x + = x.
