cangrepp

Some cryptographic attacks
Log | Files | Refs | README

smallfactor.c (950B)

      1 #include "smallfactor.h"
      2 
      3 size_t
      4 smallfactor_euclidean(ctx_t *ctx, fmpz_t out, const fmpz_t n)
      5 {
      6   assert(ctx->has_primorial);
      7   assert(ctx->nsmallprimes > 0);
      8   assert(ctx->smallprimes != NULL);
      9   size_t i;
     10 
     11   fmpz_gcd(out, n, ctx->primorial);
     12 
     13   if (fmpz_cmp_ui(out, 1) > 0 && fmpz_cmp(out, n) < 0) {
     14     // 1 < g < n
     15     return SMALLFACTOR_FOUND;
     16   } else if (fmpz_cmp(out, n) == 0) {
     17     // g = n, so n divides p
     18     if (fmpz_cmp_ui(n, 1) == 0) {
     19       // 1 only has trivial factors
     20       return SMALLFACTOR_NOT_FOUND;
     21     } else {
     22       // n is either prime or has an 8-bit prime factor, trial divide
     23       i = 0;
     24       while (fmpz_cmp_ui(&ctx->smallprimes[i], 256) < 0) {
     25         fmpz_tdiv_qr(out, &(ctx->smallprimes[i]), n,
     26                      &(ctx->smallprimes[i]));
     27 
     28         if (fmpz_cmp_ui(&(ctx->smallprimes[i]), 0) == 0) {
     29           return SMALLFACTOR_FOUND;
     30         }
     31 
     32         i++;
     33       }
     34     }
     35   }
     36 
     37   return SMALLFACTOR_NOT_FOUND;
     38 }