sieve.c

IBE是一种非对称密码技术

/* Copyright 2003-2006, Voltage Security, all rights reserved.
 */

#include "vibecrypto.h"
#include "environment.h"
#include "base.h"
#include "libctx.h"
#include "algobj.h"
#include "mpint.h"
#include "prime.h"
#include "errorctx.h"

int VoltSieveCandidate (
   VoltMpInt *primeCandidate,
   unsigned int *firstPrimes,
   unsigned int firstPrimesLen,
   unsigned char *sieve,
   unsigned int sieveSize
   )
{
  int status;
  unsigned int index, sieveIndex;
  VoltMpIntCtx *mpCtx = (VoltMpIntCtx *)(primeCandidate->mpCtx);
  VoltLibCtx *libCtx = (VoltLibCtx *)(mpCtx->voltObject.libraryCtx);
  VoltMpInt *smallPrime = (VoltMpInt *)0;
  VoltMpInt *quotient = (VoltMpInt *)0;
  VoltMpInt *remainder = (VoltMpInt *)0;
  VOLT_DECLARE_FNCT_LINE (fnctLine)

  do
  {
    /* Initialize all sieve elements to 0.
     */
    Z2Memset (sieve, 0, sieveSize);

    /* Create an MpInt to hold the small primes we're going to divide
     * by. Then create MpInt's to hold the quotient and remainder when
     * we divide.
     */
    VOLT_SET_FNCT_LINE (fnctLine)
    status = mpCtx->CreateMpInt ((Pointer)mpCtx, &smallPrime);
    if (status != 0)
      break;

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

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

    /* Go through all the primes we're going to sieve.
     */
    for (index = 0; index < firstPrimesLen; ++index)
    {
      /* Find primeCandidate / smallPrime.
       */
      VOLT_SET_FNCT_LINE (fnctLine)
      status = mpCtx->IntToMpInt (0, firstPrimes[index], smallPrime);
      if (status != 0)
        break;

      VOLT_SET_FNCT_LINE (fnctLine)
      status = mpCtx->Divide (primeCandidate, smallPrime, quotient, remainder);
      if (status != 0)
        break;

      /* Because the divisor is an unsigned int, the remainder is
       * guaranteed to be an unsigned int.
       */
      VOLT_SET_FNCT_LINE (fnctLine)
      status = mpCtx->MpIntToInt (remainder, 0, &sieveIndex);
      if (status != 0)
        break;

      /* If the remainder is 0, the first number to sieve is the
       * candidate itself, so start sieving at index 0.
       * If not 0, then candidate + (smallPrime - remain) is evenly
       * divisible by the small prime.
       * But our sieve array is every other number, so the entry
       * corresponding to candidate + (smallPrime - remain) is
       * (smallPrime - remain) / 2 elements from the beginning.
       * But if (smallPrime - remain) is odd, then we're not
       * representing that number in the sieve table (primeCandidate is
       * odd, so adding (smallPrime - remain) to primeCandidate would
       * yield an even number). That means the next entry in our table
       * that is evenly divisible by the smallPrime is a further
       * smallPrime along.
       * So the starting point is
       *    0 if remain is 0
       *    (smallPrime - remain) / 2 if (smallPrime - remain) is odd
       *    (2*smallPrime - remain) / 2 if (smallPrime - remain) is even
       */
      if (sieveIndex != 0)
      {
        sieveIndex = (unsigned int)(firstPrimes[index]) - sieveIndex;
        if ((sieveIndex & 1) == 1)
          sieveIndex += (unsigned int)(firstPrimes[index]);
        sieveIndex >>= 1;
      }

      /* Starting with the sieveIndex computed, let every smallPrime'th
       * value fall through the sieve.
       */
      while (sieveIndex < sieveSize)
      {
        sieve[sieveIndex] = 1;
        sieveIndex += (unsigned int)(firstPrimes[index]);
      }
    }
/*    if (status != 0)
      break;
 */
  } while (0);

  mpCtx->DestroyMpInt (&smallPrime);
  mpCtx->DestroyMpInt (&quotient);
  mpCtx->DestroyMpInt (&remainder);

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

  return (status);
}