Re: Easy test of surrogate factoring

From: Décio Luiz Gazzoni Filho (decio_at_decpp.removethis.net)
Date: 02/18/05 

Date: Fri, 18 Feb 2005 13:22:20 -0200

Matt Gutting wrote:
> <snip>
>
> Heck, James, *I* can write a program to factor an RSA number. How about
> this?
>
> int M;
> M = //insert the RSA number here
> for (int i=2; i<=sqrt(M);i++) {
> if (M % i = 0) {
> cout << i << " is a factor of " << M;
> }
> }

I don't think your program works, because a typical RSA number won't fit in
an integer. Try this (if you have GMP and the C++ class interface):

#include <iostream>
#include <gmpxx.h>

int main()
{
  mpz_class M(/*insert RSA number here between quotes*/);
  for(mpz_class p=2; p<=sqrt(M); mpz_nextprime(p.get_mpz_t(),p.get_mpz_t())
    if(mpz_divisible_p(M.get_mpz_t(),p.get_mpz_t())
    {
      std::cout << p << " is a factor of " << M << std::endl;
      break;
    }
  return 0;
}

I included a few optimizations, although a key would be to try backwards
from sqrt(M), because any given factors will be closer to sqrt(M) than 2.

Décio

Relevant Pages

  • Re: Easy test of surrogate factoring
    ... Matt Gutting wrote: ... I don't think your program works, because a typical RSA number won't fit in ... int main ...
    (sci.math)
  • Re: Easy test of surrogate factoring
    ... > I don't think your program works, because a typical RSA number won't fit in ... > int main ... because any given factors will be closer to sqrtthan 2. ...
    (sci.crypt)
  • [PATCH] I2C: Coding style cleanups to via686a
    ... (These conversions were contributed by Jonathan Teh Soon Yew ... int inNum) ... smooth function fit to the data will allow us to get better precision. ... - VIA register values 0-255. ...
    (Linux-Kernel)
  • Re: Use of large field definitions for small values
    ... but the field is actually defined as int or even larger as bigint. ... Less data can fit in a page....This will degrade performance. ... Let say we have a single column table which is BigInt which you could ... Now abt the CPU. ...
    (comp.databases.ms-sqlserver)
  • Re: No accessible overloaded
    ... called (int, string, int, int). ... (obviously the conversion works OK). ... Dim ii As Integer = ss ... Even though it is obvious to us that 32 will fit in a Short, the compiler pretty much only works one line at a time, and all it sees is that you are trying to fit a quart in a pint pot. ...
    (microsoft.public.dotnet.languages.vb)