mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2003-12-30, 20:25   #1
dsouza123
 
dsouza123's Avatar
 
Sep 2002

2×331 Posts
Default New program to test a single factor

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.)
Attached Files
File Type: zip tfactor1.zip (14.4 KB, 341 views)
dsouza123 is offline   Reply With Quote
Old 2003-12-31, 12:54   #2
dsouza123
 
dsouza123's Avatar
 
Sep 2002

2·331 Posts
Default

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

Code:
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 is offline   Reply With Quote
Old 2003-12-31, 18:52   #3
dsouza123
 
dsouza123's Avatar
 
Sep 2002

2·331 Posts
Default

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 is offline   Reply With Quote
Old 2004-01-03, 05:05   #4
dsouza123
 
dsouza123's Avatar
 
Sep 2002

2·331 Posts
Default

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 is offline   Reply With Quote
Old 2004-01-03, 05:23   #5
dsouza123
 
dsouza123's Avatar
 
Sep 2002

10100101102 Posts
Default

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.
Attached Files
File Type: zip tfactora.zip (5.6 KB, 296 views)
dsouza123 is offline   Reply With Quote
Old 2004-01-13, 02:29   #6
dsouza123
 
dsouza123's Avatar
 
Sep 2002

2×331 Posts
Default

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 is offline   Reply With Quote
Old 2004-01-13, 03:53   #7
dsouza123
 
dsouza123's Avatar
 
Sep 2002

2×331 Posts
Default

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.
Attached Files
File Type: zip tfactorb.zip (17.8 KB, 326 views)
dsouza123 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
My factor program... Xyzzy Programming 18 2014-07-26 15:42
New program to fully factor with GMP-ECM rogue GMP-ECM 51 2009-06-01 12:53
C program to factor using GMP-ECM and msieve lazy GMP-ECM 6 2007-06-16 18:12
Program to factor F14 dsouza123 Programming 79 2006-01-23 11:42
4 checkins in a single calendar month from a single computer Gary Edstrom Lounge 7 2003-01-13 22:35

All times are UTC. The time now is 00:38.


Tue Jun 28 00:38:16 UTC 2022 up 74 days, 22:39, 1 user, load averages: 1.64, 1.40, 1.35

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔