/* The Rabin-Miller test starts out by representing the prime
     * candidate as
     *    candidate = 1 + (mVal * 2^expo)
     * This is what's going on.
     *    Find candidate - 1, this is an even number (candidate is odd)
     *    How many trailing 0's are there in the binary representation
     *      of candidate - 1. That's expo.
     *    Shift candidate right expo bits, that's now mVal.
     */
    VOLT_SET_ERROR_TYPE (errorType, 0)
    VOLT_SET_FNCT_LINE (fnctLine)
    status = mpCtx->CreateMpInt ((Pointer)mpCtx, &mVal);
    if (status != 0)
      break;

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

    /* Find primeCandidate - 1. We'll use it for comparison purposes
     * later.
     */
    VOLT_SET_FNCT_LINE (fnctLine)
    status = mpCtx->CreateMpInt ((Pointer)mpCtx, &candidateMinusOne);
    if (status != 0)
      break;

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

    VOLT_SET_FNCT_LINE (fnctLine)
    status = mpCtx->SetBit (candidateMinusOne, 0, 0);
    if (status != 0)
      break;

    VOLT_SET_FNCT_LINE (fnctLine)
    status = mpCtx->CreateMpInt ((Pointer)mpCtx, &randVal);
    if (status != 0)
      break;

    VOLT_SET_FNCT_LINE (fnctLine)
    status = mpCtx->CreateMpInt ((Pointer)mpCtx, &zVal);
    if (status != 0)
      break;

    /* Find the number of trailing 0's. After subtracting 1, the 0'th
     * bit is 0, so start looking at bit position 1. Use index as a
     * temp variable.
     */
    for (expo = 1; expo < primeSizeBits; ++expo)
    {
      VOLT_SET_FNCT_LINE (fnctLine)
      status = mpCtx->GetBit (mVal, expo, &index);
      if (status != 0)
        break;
      if (index == 1)
        break;
    }

    VOLT_SET_ERROR_TYPE (errorType, VT_ERROR_TYPE_PRIMARY)
    VOLT_SET_FNCT_LINE (fnctLine)
    if (expo >= primeSizeBits)
      status = VT_ERROR_MP_INT_RANGE;
    if (status != 0)
      break;

    /* Step 2, find expo and mVal, we have expo, but the MpInt mVal is
     * currently equal to candidate - 1. Shift it right expo bits and
     * we have mVal.
     */
    VOLT_SET_ERROR_TYPE (errorType, 0)
    VOLT_SET_FNCT_LINE (fnctLine)
    status = mpCtx->ShiftRightBits (mVal, expo);
    if (status != 0)
      break;

    /* Perform the Rabin-Miller algorithm the prescribed number of
     * times.
     */
    for (index = 0; index < iterationCount; ++index)
    {
      /* Step 3, get a random number < candidate.
       */
      VOLT_SET_FNCT_LINE (fnctLine)
      status = GetRandomValue (
        libCtx, mpCtx, primeCandidate, buffer, bufferSize);
      if (status != 0)
        break;

      VOLT_SET_FNCT_LINE (fnctLine)
      buffer[0] &= 0x7f;
      status = mpCtx->OctetStringToMpInt (0, buffer, bufferSize, randVal);
      if (status != 0)
        break;

      /* Step 4, find zVal = (randVal ^ mVal) mod candidate
       */
      VOLT_SET_FNCT_LINE (fnctLine)
      status = mpCtx->ModExp (randVal, mVal, primeCandidate, zVal);
      if (status != 0)
        break;

      /* Step 5, if zVal == 1 or zVal == candidate - 1, the test passes
       * this iteration.
       */
      VOLT_SET_FNCT_LINE (fnctLine)
      status = mpCtx->MpIntToInt (zVal, 1, &value);
      if (status != VT_ERROR_MP_INT_RANGE)
      {
        if (status != 0)
          break;

        if (value == 1)
          continue;
      }
      else
      {
        VOLT_SET_FNCT_LINE (fnctLine)
        status = mpCtx->Compare (zVal, candidateMinusOne, &compareResult);
        if (status != 0)
          break;

        if (compareResult == 0)
          continue;
      }

      /* Step 6, square zVal, make a comparison (step 5), then loop.
       */
      for (count = 1; count < expo; ++count)
      {
        VOLT_SET_FNCT_LINE (fnctLine)
        status = mpCtx->Square (zVal, randVal);
        if (status != 0)
          break;

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

        /* Step 5 comparison, if zVal now == candidate - 1, this
         * iteration passes, move on to the next random number.
         */
        VOLT_SET_FNCT_LINE (fnctLine)
        status = mpCtx->Compare (zVal, candidateMinusOne, &compareResult);
        if (status != 0)
          break;

        if (compareResult == 0)
          break;

        /* If zVal is now 1, we know the candidate is not prime.
         */
        VOLT_SET_FNCT_LINE (fnctLine)
        status = mpCtx->MpIntToInt (zVal, 1,&value);
        if (status != VT_ERROR_MP_INT_RANGE)
        {
          if (status != 0)
            break;

          /* Set expo to count to skip the rest of the zVal^2 tests, we
           * know the number is not prime.
           */
          if (value == 1)
            count = expo;
        }
        status = 0;
      }
      if (status != 0)
        break;

      /* If we broke out of the step 6 loop early, the comparison was
       * equal, we can move on to the next iteration.
       * If we looped step 6 every time and found no match, this number
       * is not prime. Exit the Rabin-Miller iterations.
       */
      if (count >= expo)
        break;
    }
    if (status != 0)
      break;

    /* If we didn't break out of the loop early, we did every
     * iteration, which means the number passes.
     */
    if (index >= iterationCount)
      *isPrime = 1;

  } while (0);

  /* We cleared the low order bit for comparison purposes, set it back.
   */
  mpCtx->SetBit (primeCandidate, 0, 1);

  if (buffer != (unsigned char *)0)
    Z2Free (buffer);

  mpCtx->DestroyMpInt (&candidateMinusOne);
  mpCtx->DestroyMpInt (&mVal);
  mpCtx->DestroyMpInt (&zVal);
  mpCtx->DestroyMpInt (&randVal);

  VOLT_LOG_ERROR_COMPARE (
    status, (VtLibCtx)libCtx, status, errorType, fnctLine,
    "VoltRabinMillerTest", (char *)0)

  return (status);
}

int VoltCheckRelativePrime (
   VoltMpIntCtx *mpCtx,
   VoltMpInt *relativePrime,
   VoltMpInt *prime,
   VoltMpInt *temp1,
   VoltMpInt *temp2,
   unsigned int *relPrime
   )
{
  int status;
  unsigned int bitLen;
  VOLT_DECLARE_FNCT_LINE (fnctLine)

  /* Initialize to true, if they turn out not to be relatively prime,
   * we'll reset it.
   */
  *relPrime = 1;

  do
  {
    /* Find prime / relativePrime. If the remainder is 1, then p - 1
     * would not be relatively prime.
     */
    VOLT_SET_FNCT_LINE (fnctLine)
    status = mpCtx->Divide (prime, relativePrime, temp1, temp2);
    if (status != 0)
      break;

    /* If the bitLen of the remainder is not 1, the remainder cannot be
     * 1, so the values are relatively prime.
     */
    VOLT_SET_FNCT_LINE (fnctLine)
    status = mpCtx->GetBitLength (temp2, &bitLen);
    if (status != 0)
      break;

    if (bitLen != 1)
      break;

    /* The bit length is 1, but there is a very slight chance that the
     * remainder is 0. That would mean prime (actually a prime
     * candidate) is a multiple of relativePrime. Even though the
     * chance is slim, we have to program for the possibility.
     * Use bitLen as a temp variable.
     */
    VOLT_SET_FNCT_LINE (fnctLine)
    status = mpCtx->GetBit (temp2, 0, &bitLen);
    if (status != 0)
      break;

    /* If the bit is 0, the remainder is 0, so p - 1 and relativePrime
     * are indeed relatively prime.
     */
    if (bitLen != 0)
      *relPrime = 0;

  } while (0);

  VOLT_LOG_ERROR_INFO_COMPARE (
    status, 0, mpCtx, status, 0, 0,
    (char *)0, "VoltCheckRelativePrime", fnctLine, (char *)0)

  return (status);
}

static int GetRandomValue (
   VoltLibCtx *libCtx,
   VoltMpIntCtx *mpCtx,
   VoltMpInt *primeCandidate,
   unsigned char *buffer,
   unsigned int bufferLen
   )
{
  int status;
  unsigned int sign, pLen, bytesNeeded, copyCount, offset, digestLen;
  VtAlgorithmObject digester = (VtAlgorithmObject)0;
  unsigned char *pBuf = (unsigned char *)0;
  unsigned char digest[20];
  VOLT_DECLARE_ERROR_TYPE (errorType)
  VOLT_DECLARE_FNCT_LINE (fnctLine)

  do
  {
    /* Get the primeCandidate into a buffer.
     */
    VOLT_SET_ERROR_TYPE (errorType, 0)
    VOLT_SET_FNCT_LINE (fnctLine)
    status = mpCtx->MpIntToOctetString (
      primeCandidate, &sign, (unsigned char *)0, 0, &pLen);
    if (status == 0)
      status = VT_ERROR_GENERAL;
    if (status != VT_ERROR_BUFFER_TOO_SMALL)
      break;

    VOLT_SET_ERROR_TYPE (errorType, VT_ERROR_TYPE_PRIMARY)
    VOLT_SET_FNCT_LINE (fnctLine)
    status = VT_ERROR_MEMORY;
    pBuf = (unsigned char *)Z2Malloc (pLen, VOLT_MEMORY_SENSITIVE);
    if (pBuf == (unsigned char *)0)
      break;

    VOLT_SET_ERROR_TYPE (errorType, 0)
    VOLT_SET_FNCT_LINE (fnctLine)
    status = mpCtx->MpIntToOctetString (
      primeCandidate, &sign, pBuf, pLen, &pLen);
    if (status != 0)
      break;

    status = VtCreateAlgorithmObject (
      (VtLibCtx)libCtx, VtAlgorithmImplSHA1, (Pointer)0, &digester);
    if (status != 0)
      break;

    /* As long as there are bytes needed, digest.
     */
    bytesNeeded = bufferLen;
    offset = 0;
    do
    {
      copyCount = bytesNeeded;
      if (bytesNeeded >= 20)
        copyCount = 20;
      bytesNeeded -= copyCount;

      status = VtDigestInit (digester);
      if (status != 0)
        break;

      status = VtDigestUpdate (digester, pBuf, pLen);
      if (status != 0)
        break;

      status = VtDigestFinal (
        digester, buffer, bufferLen, digest, sizeof (digest), &digestLen);
      if (status != 0)
        break;

      Z2Memcpy (buffer + offset, digest, copyCount);
      offset += copyCount;

    } while (bytesNeeded != 0);

  } while (0);

  Z2Memset (digest, 0, sizeof (digest));

  if (pBuf != (unsigned char *)0)
    Z2Free (pBuf);

  VtDestroyAlgorithmObject (&digester);

  VOLT_LOG_ERROR_COMPARE (
    status, (VtLibCtx)libCtx, status, errorType, fnctLine,
    "GetRandomValue", (char *)0)

  return (status);
}