lucas.c

IBE是一种非对称密码技术

      status = mpCtx->ModReduce (newU, primeCandidate, newV);
      if (status != 0)
        break;

      /* Now compute (U + V) / 2 mod N
       */
      VOLT_SET_FNCT_LINE (fnctLine)
      status = mpCtx->Add (VVal, UVal, newU);
      if (status != 0)
        break;

      VOLT_SET_FNCT_LINE (fnctLine)
      status = mpCtx->GetBit (newU, 0, &getBit);
      if (status != 0)
        break;

      if (getBit == 1)
      {
        VOLT_SET_FNCT_LINE (fnctLine)
        status = mpCtx->Add (primeCandidate, newU, newU);
        if (status != 0)
          break;
      }

      VOLT_SET_FNCT_LINE (fnctLine)
      status = mpCtx->ShiftRightBits (newU, 1);
      if (status != 0)
        break;

      VOLT_SET_FNCT_LINE (fnctLine)
      status = mpCtx->ModReduce (newU, primeCandidate, UVal);
      if (status != 0)
        break;

      VOLT_SET_FNCT_LINE (fnctLine)
      status = mpCtx->MpIntToMpInt (newV, VVal);
      if (status != 0)
        break;
    }

    /* When we've gone through all the bits of N + 1, if U is 0, the
     * candidate passes the test.
     */
    VOLT_SET_FNCT_LINE (fnctLine)
    status = mpCtx->EvenOddZeroPositiveNegative (UVal, &getZero);
    if (status != 0)
      break;

    if (getZero == 0)
      *isPrime = 1;

  } while (0);

  mpCtx->DestroyMpInt (&newU);
  mpCtx->DestroyMpInt (&newV);
  mpCtx->DestroyMpInt (&UVal);
  mpCtx->DestroyMpInt (&VVal);
  mpCtx->DestroyMpInt (&NPlus1);
  mpCtx->DestroyMpInt (&DValue);

  VOLT_LOG_ERROR_INFO_COMPARE (
    status, 0, mpCtx, status, 0, errorType,
    (char *)0, "VoltLucasTest", fnctLine, (char *)0)

  return (status);
}

#define FIND_DVALUE_LIMIT 256

static int FindLucasDValue (
   VoltMpInt *primeCandidate,
   VoltMpInt *DValue,
   VoltMpInt *temp1,
   VoltMpInt *temp2,
   unsigned int *valueFound
   )
{
  int status, currentD, currentSign, jacobi;
  unsigned int index, limit;
  VoltMpIntCtx *mpCtx = (VoltMpIntCtx *)(primeCandidate->mpCtx);
  VOLT_DECLARE_ERROR_TYPE (errorType)
  VOLT_DECLARE_FNCT_LINE (fnctLine)

  *valueFound = 0;

  do
  {
    VOLT_SET_ERROR_TYPE (errorType, VT_ERROR_TYPE_PRIMARY)

    /* Try the D possibilities. Keep trying until we run out of
     * possibilities.
     * Start with 5 and a positive sign, then increment by 2 and
     * alternate between positive and negative.
     */
    limit = FIND_DVALUE_LIMIT;
    currentSign = 0;
    currentD = 5;
    for (index = 0; index < limit; ++index)
    {
      /* If 0, the sign is positive, DValue is the currentD.
       */
      if (currentSign == 0)
      {
        VOLT_SET_FNCT_LINE (fnctLine)
        status = mpCtx->IntToMpInt (0, currentD, DValue);
        if (status != 0)
          break;
      }
      else
      {
        /* If currentSign is not 0, the d possibility is negative, we
         * want p - d.
         */
        VOLT_SET_FNCT_LINE (fnctLine)
        status = mpCtx->IntToMpInt (0, currentD, temp2);
        if (status != 0)
          break;

        VOLT_SET_FNCT_LINE (fnctLine)
        status = mpCtx->Subtract (primeCandidate, temp2, DValue);
        if (status != 0)
          break;
      }

      /* Find the Jacobi of this D candidate.
       */
      VOLT_SET_FNCT_LINE (fnctLine)
      status = FindJacobi (DValue, primeCandidate, temp1, temp2, &jacobi);
      if (status != 0)
        break;

      /* If the Jacobi is -1, we have our D.
       */
      if (jacobi == -1)
        break;

      /* The new sign. If it is currently 0, it will become 1, if it is
       * 1, it will become 0.
       */
      currentSign ^= 1;
      currentD += 2;
    }
    if (status != 0)
      break;

    /* If we went through the list and found no D, return, status is 0
     * and valueFound is 0. If we didn't go through the list, we found
     * our D, change valueFound to 1.
     */
    if (index < limit)
      *valueFound = 1;

  } while (0);

  VOLT_LOG_ERROR_INFO_COMPARE (
    status, 0, mpCtx, status, 0, errorType,
    (char *)0, "FindLucasDValue", fnctLine, (char *)0)

  return (status);
}

static int FindJacobi (
   VoltMpInt *aVal,
   VoltMpInt *nVal,
   VoltMpInt *temp1,
   VoltMpInt *temp2,
   int *jacobi
   )
{
  int status, aStatus, jReturn;
  unsigned int bit1, bit2;
  VoltMpIntCtx *mpCtx = (VoltMpIntCtx *)(nVal->mpCtx);
  VoltMpInt *swap, *a, *n;
  VOLT_DECLARE_ERROR_TYPE (errorType)
  VOLT_DECLARE_FNCT_LINE (fnctLine)

  jReturn = 1;

  do
  {
    /* Set a to the incoming aVal and n to the incoming nVal.
     */
    a = temp1;
    n = temp2;

    VOLT_SET_ERROR_TYPE (errorType, 0)
    VOLT_SET_FNCT_LINE (fnctLine)
    status = mpCtx->MpIntToMpInt (aVal, a);
    if (status != 0)
      break;

    VOLT_SET_FNCT_LINE (fnctLine)
    status = mpCtx->MpIntToMpInt (nVal, n);
    if (status != 0)
      break;

    VOLT_SET_FNCT_LINE (fnctLine)
    status = mpCtx->EvenOddZeroPositiveNegative (a, &aStatus);
    if (status != 0)
      break;

    /* While a != 0, keep looping.
     */
    while (aStatus != 0)
    {
      /* We're going to need to know either or both of n mod 8 and
       * n mod 4. We know that n is odd, so bit 0 is 1. Get bits 1 and
       * 2.
       * If bits 1 and 2 are 1, then n mod 8 is 7
       * If bits 1 and 2 are 0, then n mod 8 is 1
       * If bit 1 is 1 and bit 2 is 0, then n mod 8 is 3
       * If bit 1 is 0 and bit 2 is 1, then n mod 8 is 5
       */
      VOLT_SET_FNCT_LINE (fnctLine)
      status = mpCtx->GetBit (n, 1, &bit1);
      if (status != 0)
        break;

      VOLT_SET_FNCT_LINE (fnctLine)
      status = mpCtx->GetBit (n, 2, &bit2);
      if (status != 0)
        break;

      /* If a is even, divide by two and do some extra work until it is
       * odd.
       */
      while ((aStatus & 1) == 0)
      {
        VOLT_SET_FNCT_LINE (fnctLine)
        status = mpCtx->ShiftRightBits (a, 1);
        if (status != 0)
          break;

        /* If n mod 8 is 3 or 5, j = -j.
         */
        if (bit1 != bit2)
          jReturn = -jReturn;

        VOLT_SET_FNCT_LINE (fnctLine)
        status = mpCtx->EvenOddZeroPositiveNegative (a, &aStatus);
        if (status != 0)
          break;
      }

      /* Swap a and n.
       */
      swap = a;
      a = n;
      n = swap;

      /* If a mod 4 is 3 and n mod 4 is 3, then j = -j.
       * We know both n and a are odd, we have bit1 of a (it was n), so
       * get bit1 of n.
       */
      VOLT_SET_FNCT_LINE (fnctLine)
      status = mpCtx->GetBit (n, 1, &bit2);
      if (status != 0)
        break;

      /* If both the bits we got are 1, both numbers are 3 mod 4.
       */
      if ( (bit1 == 1) && (bit2 == 1) )
        jReturn = -jReturn;

      /* a = a mod n.
       */
      VOLT_SET_FNCT_LINE (fnctLine)
      status = mpCtx->ModReduce (a, n, a);
      if (status != 0)
        break;

      VOLT_SET_FNCT_LINE (fnctLine)
      status = mpCtx->EvenOddZeroPositiveNegative (a, &aStatus);
      if (status != 0)
        break;
    }

    /* When a == 0, we're done. Just one more check. If n == 1, then
     * return j. If not, return 0.
     */
    VOLT_SET_FNCT_LINE (fnctLine)
    status = mpCtx->MpIntToInt (n, 0, &aStatus);
    if (status != 0)
    {
      if (status != VT_ERROR_MP_INT_RANGE)
        break;

      /* If the error was RANGE, then n is not 1.
       */
      aStatus = 2;
      status = 0;
    }

    if (aStatus != 1)
      jReturn = 0;

  } while (0);

  *jacobi = jReturn;

  VOLT_LOG_ERROR_INFO_COMPARE (
    status, 0, mpCtx, status, 0, errorType,
    (char *)0, "FindJacobi", fnctLine, (char *)0)

  return (status);
}