New program to test a single factor

[dsouza123]

Attached is a new program TFactor version 1.0
( 32 bit Windows program, Delphi/Pascal source code, batch file used to compile with Delphi 4)

It requests the exponent, p in 2^p - 1 and a potential factor.

The result is either it is factor or it isn't.

The current code can handle a 32 bit p 4294967295 max
and a factor of about 250 digits/ 860 bits.

It can easily be expanded to 1024 bit factor just by changing the number of (longword/dword/unsigned 32 bit integer)s to 31 instead of the 26 it currently has. Array 0..26 of longword.

It is console mode ( doesn't have a windows GUI ).

The powmod function is slow, should/will be replaced by a powering function.

Some extra functions not used, convert the binary longword array to a hexadecimal string, convert to a decimal string. (The decimal string conversion only works if the factor fits in one 32 bit longword.)

[dsouza123]

Found a bug in the BigtoHStr, which isn't used so it doesn't affect the compiled program.

Procedure BigToHStr(n:lwarr; var s:string); // binary array to positive hexadecimal string
var
  i,j,k : integer;
  has : integer;
  c : char;

begin
  s := '                                    ';
  s := '';
  has := -1;
  for i := 0 to lwhi do
    if n[i] > 0 then
      has := i;
  if (has = -1) then
    s := '0'
  else
    for i := 0 to has do           // once for each used cell/longword
      for j := 0 to 7 do begin   // 7 is correct   had  lwhi  in error
        k := n[i] mod 16;
        if (k < 10) then
          c := chr(k+48)
        else
          c := chr(k+65-10);
        if not((i = has) and (n[i] = 0)) then
          s := c + s;
        n[i] := n[i] div 16;
      end;
  s := '$' + s;
end;

The powering procedure is nearly done just need an efficient mod.

[dsouza123]

Suggestions requested for an efficient mod function.

The powering algorithm works but the mod function is very slow.

It takes a number N and the factor F and does the mod by repeated subtractions which is too slow.
N is the result from the previous iteration squared and if a one bit in the exponent P for the current bit then times two.

F=23
iteration 3 result is 9
iteration 4 9^2 = 81; bit = 1 81*2= 162; N =162, N mod F, 162 mod 23 = 1

When N and F are large is the issue. Is there a short cut using the previous iterations result 9 ? Or the F - result 9 ?
Is there a rough estimate to get a multiplier times F that would put it very close to N.

Example:
23 - 9 = 14 14 / 2 = 7 F * 7 = 161 N = 9*9*2 = 162 162 - 161 = 1 162 mod 23 = 1
Is this workable or just a fluke ?

Any ideas ?

The functions available are :
Subtraction though only a larger - smaller ( equal will also work but a compare before with a zeroing of the result is quicker).
Square, multiply, times2 ( shift left 1 bit)
Addition.
A div2 could be written ( shift right 1 bit)

All are positive integer (array of 32 bit longwords) numbers.

I have thought of shifting F until larger then N then backing up (using previous N) and subtracting, then repeating until N is less than F.
I think it would still be too slow.

[dsouza123]

Progressing in the code with invaluable help from Cyclamen Persicum and Wacky.

Cyclamen has been gracious enough to supply theory/example/code for
Montgomery modular reduction. I am working through it.

Wacky came up with a formula to approximate the mod. I've coded it but there are
bugs (probably in routines it calls) because it only gives correct answers for numbers
small enough to fit in one 32-bit longword.

( Need to test the other functions better
add,sub,mult,times2,div2,shiftleft32,shiftright32,compare and modlw itself. )

Any ideas on tests to setup to stress test them ?

[dsouza123]

Oops forgot to mention square, powmod functions.

The powmod works on all the numbers I have used but it is extremely slow.

The code is messy right now, alot of debugging lines but I'll post
it anyway.

TFactorA because alot is alpha code.

[dsouza123]

It is working now, it agrees with the mersennes and their factors that I have that were found with Prime95,
ewmayer's program ( which found a very large exponent mersenne) and the mersenne with the record size factor
(from the page geoff provided the link for http://www.loria.fr/~zimmerma/records/Pminus1.html )
and some very small mersennes (2^11-1 with factor 23 for example).

I replaced/rewrote some of the procedures/functions.

The multiplication routine had a bug which sometimes gave the wrong answer, it is replaced with completely different code.

The BigToDStr routine (create the base10 (decimal) string for a large binary integer) is replaced,
the previous one worked correctly only with small numbers ( less than 2^32, one 32 bit longword ).

The modlw is working though it requires multiple passes for the larger numbers.

The size of the exponent p ( 2^p - 1 ) has been increased to take a 256 bit integer number.

It is much quicker now, using the powering routine it takes about a second to evaluate a number instead of the minutes
it takes with the powmod function.

The square routine has been replaced with a call to the multiplication routine.

I am going to clean out the debugging code and post a clean copy of the source along with the compiled program.

Things to do:

Optimize it slightly, it currently checks the full size of the large integer for most functions instead of stopping at the size
that the number occupies.

Get the Montgomery modular reduction that Cyclamen Persicum explained and provided some code for,
to work with the large number routines ( 32 anary based ). Maybe use the technique that alpertron mentioned.

Convert an integer square root routine in another large integer library I have to work in this one.

[dsouza123]

I have attached the cleaned up source code ( TFactorB.pas ) with the compiled program ( TFactorB.exe ).

With this program a very large potential factor of an enormous mersenne can be tested, on a computer running a version Windows 32-bit ( tested on 98SE and XP Pro ).

It has been tested with a handfull of mersennes with their known factors and with some non factors.