Re: Easy test of surrogate factoring
From: Marcel Martin (mm_at_nowhere.net)
Date: 02/19/05
- Next message: Morten Reistad: "Re: Thou shalt have no other gods before the ANSI C standard"
- Previous message: Tim Peters: "Re: Factoring, sf, and reasonable requests"
- In reply to: Décio Luiz Gazzoni Filho: "Re: Easy test of surrogate factoring"
- Next in thread: Décio Luiz Gazzoni Filho: "Re: Easy test of surrogate factoring"
- Reply: Décio Luiz Gazzoni Filho: "Re: Easy test of surrogate factoring"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: Sat, 19 Feb 2005 08:54:34 +0100
Décio Luiz Gazzoni Filho wrote:
> 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.
Not sure. There are as much integers between 1 and 2^k
than between 2^k + 1 and 2^(k+1).
So, if (BinarySize(Sqrt) - BinarySize(Factor)) > 1 holds
then Factor is closer to 2 than to Sqrt.
mm
- Next message: Morten Reistad: "Re: Thou shalt have no other gods before the ANSI C standard"
- Previous message: Tim Peters: "Re: Factoring, sf, and reasonable requests"
- In reply to: Décio Luiz Gazzoni Filho: "Re: Easy test of surrogate factoring"
- Next in thread: Décio Luiz Gazzoni Filho: "Re: Easy test of surrogate factoring"
- Reply: Décio Luiz Gazzoni Filho: "Re: Easy test of surrogate factoring"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
