Botan  1.11.15
src/lib/math/numbertheory/ressol.cpp
Go to the documentation of this file.
00001 /*
00002 * Shanks-Tonnelli (RESSOL)
00003 * (C) 2007-2008 Falko Strenzke, FlexSecure GmbH
00004 * (C) 2008 Jack Lloyd
00005 *
00006 * Botan is released under the Simplified BSD License (see license.txt)
00007 */
00008 
00009 #include <botan/numthry.h>
00010 #include <botan/reducer.h>
00011 
00012 namespace Botan {
00013 
00014 /*
00015 * Shanks-Tonnelli algorithm
00016 */
00017 BigInt ressol(const BigInt& a, const BigInt& p)
00018    {
00019    if(a < 0)
00020       throw Invalid_Argument("ressol(): a to solve for must be positive");
00021    if(p <= 1)
00022       throw Invalid_Argument("ressol(): prime must be > 1");
00023 
00024    if(a == 0)
00025       return 0;
00026    if(p == 2)
00027       return a;
00028 
00029    if(jacobi(a, p) != 1) // not a quadratic residue
00030       return -BigInt(1);
00031 
00032    if(p % 4 == 3)
00033       return power_mod(a, ((p+1) >> 2), p);
00034 
00035    size_t s = low_zero_bits(p - 1);
00036    BigInt q = p >> s;
00037 
00038    q -= 1;
00039    q >>= 1;
00040 
00041    Modular_Reducer mod_p(p);
00042 
00043    BigInt r = power_mod(a, q, p);
00044    BigInt n = mod_p.multiply(a, mod_p.square(r));
00045    r = mod_p.multiply(r, a);
00046 
00047    if(n == 1)
00048       return r;
00049 
00050    // find random non quadratic residue z
00051    BigInt z = 2;
00052    while(jacobi(z, p) == 1) // while z quadratic residue
00053       ++z;
00054 
00055    BigInt c = power_mod(z, (q << 1) + 1, p);
00056 
00057    while(n > 1)
00058       {
00059       q = n;
00060 
00061       size_t i = 0;
00062       while(q != 1)
00063          {
00064          q = mod_p.square(q);
00065          ++i;
00066          }
00067 
00068       if(s <= i)
00069          return -BigInt(1);
00070 
00071       c = power_mod(c, BigInt::power_of_2(s-i-1), p);
00072       r = mod_p.multiply(r, c);
00073       c = mod_p.square(c);
00074       n = mod_p.multiply(n, c);
00075       s = i;
00076       }
00077 
00078    return r;
00079    }
00080 
00081 }