Constant-time factoring algorithm in C++ discovered
Rudi Cilibrasi
Hi folks,
I've just finished writing a constant-time factoring algorithm.
(well, log-time, really, since it has to print out the answer, but
that's just being picky) When run, it prints out a non-trivial
factor of the number to be factored. (hardcoded at compile time
for maximum efficiency) Does this mean public-key cryptography
is no longer secure, now that factoring is an easy problem? :)
I think this program says something about the C++ language. :)
Comments welcome...
-Rudi Cilibrasi
cili...@ugcs.caltech.edu
----------------------factor.cc--------------------------
// Constant-time factoring algorithm by Rudi Cilibrasi (2-14-96)
// cili...@ugcs.caltech.edu
//
// To compile, use gcc factor.cc -o factor -lstdc++ -lg++
// To run, just type ./factor
// This program makes extensive use of templates, thus your compiler
// must support them well. Gnu's gcc version 2.7.2 is recommended.
//
// To change the number to be factored, simply switch the #define below,
// and then recompile. (or use -D on the compile command line)
//
// Note that the size of the number which you can factor is limited
// by the size of integers on your system. (typically 32 or 64 bits)
//
// To convince yourself that the algorithm is really constant-time,
// take a look at main(). It calls only one trivial function.
//
// Because of all the template functions, compilation can be a bit
// slow. :) Have fun!
// Don't make this a prime or negative number!
#ifndef TO_BE_FACTORED
// If you don't define your own number, this default, 911*929, is used.
#define TO_BE_FACTORED 846319
#endif
#include <iostream.h>
template <long long x, long long y, long long n, long long q,
long long s, long long pa, long long pb> void zug
(long long o[1][1][x][y][n][q][s][pa][pb])
{
long long z[1][2][((x-1)*(x-1)+s)%n+1][((((y-1)*(y-1)+s)%n)
*(((y-1)*(y-1)+s)%n)+s)%n+1][n][(((q-1)*(x-y))%n+n)%n+1][s][pa][pb];
zug(z);
}
template <long long x, long long y, long long n, long long q,
long long s, long long pa, long long pb> void zug
(long long o[1][2][x][y][n][q][s][pa][pb])
{
long long z[1][3][x][y][n][q==1?2:q][q==1?s+1:s][n][q==1?1:q-1];
zug(z);
}
template <long long x, long long y, long long n, long long q,
long long s, long long pa, long long pb> void zug
(long long o[1][3][x][y][n][q][s][pa][pb])
{
long long z[1][pa%pb?3:4][x][y][n][q][s][pa%pb?pb:pa][pa%pb?pa%pb:pb];
zug(z);
}
template <long long x, long long y, long long n, long long q,
long long s, long long pa, long long pb> void zug
(long long o[1][4][x][y][n][q][s][pa][pb])
{
long long z[1][pb==1?1:5][x][y][n][q][s][pa][pb];
zug(z);
}
template <long long x, long long y, long long n, long long q,
long long s, long long pa, long long pb> void zug
(long long o[1][5][x][y][n][q][s][pa][pb])
{
static int flag1 = 0xf00dd00d, tunnela = pb, flag2 = 0xf00dd00d;
}
template <long long n> void R(long long x[1][n])
{
long long z[1][n%2?1:5][1][1][n][2][1][1][2];
zug(z);
}
int *marker(void)
{
static int marker_i=1;
return &marker_i;
}
int main()
{
long long (*base)[TO_BE_FACTORED]; // No storage actually allocated.
if (2 == 3)
R(base); // Never actually called at runtime, since 2 != 3.
int *marked;
marked = marker(); // This is constant-time, see def'n of marker above
int answer;
if (marked[1] == 0xf00dd00d)
answer = marked[2];
else if (marked[-1] == 0xf00dd00d)
answer = marked[-2];
else
{
cerr << "Sorry, compiler or architecture not supported.\n";
return 1;
}
cout << "The factor is " << answer << endl;
return 0;
}
Henry Baker
(Rudi Cilibrasi) wrote:
> I've just finished writing a constant-time factoring algorithm.
> (well, log-time, really, since it has to print out the answer, but
> that's just being picky) When run, it prints out a non-trivial
> factor of the number to be factored. (hardcoded at compile time
> for maximum efficiency) Does this mean public-key cryptography
> is no longer secure, now that factoring is an easy problem? :)
>
> I think this program says something about the C++ language. :)
> Comments welcome...
Cute.
Now if you did this in Ada or Common Lisp, you could take advantage of
'bignums'. (Yes, Ada forces the _compiler_ to do all arithmetic in
arbitrary precision -- including arbitrary precision rational arithmetic.
One of the few things Ada got right, because it guarantees portability
of cross-compilers.)
--
www/ftp directory:
ftp://ftp.netcom.com/pub/hb/hbaker/home.html