factoring big nums by HCF highest common factor.
19.07.99  08:47  am. nzst
sci.math, comp.sys.acorn.apps

posted under my recent thread:
factoring 5-byte integers ??, order 999,999,999,999,999
Reply Miracle high precision package.

ref  >  pgms.ProgramsPD.maths.BigNum.hicommnfac.tor //
attach.  prog facthcff.bas
---------------------------------------

The maximum integer in BBC Basic is 2E9 = 2^31-1.
However, larger integer values can be obtained
in BASIC64 Reals, which include 5-byte mantissa
plus 3-byte exponent.
2^(5*8) = 1.099E12.

I have factored numbers order 1E15-1 etc. without
using arrays of integers.

Results ..

enter no. / expression  . Qq/ 0 <CR> = quit  ?1E15-1
1E15-1 = 999999999999999

proc Hhcf(x = 999999999999999

 HCF = 3
999999999999999  Factor = 3 * 333333333333333
3 * 1
1 prime.           centisec = 8

 HCF = 3441
333333333333333  Factor = 3441 * 96871064613
3 * 1147
31 * 37
37 prime.          centisec = 13

 HCF = 123
96871064613  Factor = 123 * 787569631
3 * 41
41 prime.          centisec = 16
271 * 2906161
2906161 prime.     centisec = 95


The following program segment divides out odd factors
j of x.  It assumes x , j < 2E9.

DEF PROCfast
j = 3
REPEAT
	WHILE x MOD j = 0
	x = x/j  :  PRINT j " * " x
	ENDWHILE
	j = j+2
	UNTIL j*j > x

However, if x > 2E9, Then I need to use

DEF PROCsplit
x = x - INT( x/j)  :  REM Integer part, Floor..

which is accurate up to approximately 2^40.

Unfortunately though, if one tests beginning at
low factors j,  then  INT(x/j) may fail if
x/3 > 2E9.  e.g. too big.
It is impossible to prove a quotient exceeding 2E9.

Therefore, if x > 2E9, I calculate a safe higher
starting value for j, such that x/ j < 2E9.
If I then find two integer factors,
x = j * x1,   each factor j, x1 < 2E9 may be further
reduced very quickly by PROCfast above. (x MOD j = 0).

I do not want to test every even number to see if
it divides.  That would slow down the program.

A composite number must be either a power of 2, or it
contains an odd factor.  We are likely to find an odd
factor, sooner or later.. so I must test if x
is an exact power of 2.

T = 1
REPEAT
	IF x = T THEN PRINT "Pwr of 2."
	T = 2*T     :  REM corrected. this line should follow if.##

	UNTIL T > x

There is a further way of testing low factors.
c = 2*3*5*7*11*13*17*19*23  == 2E9.

I therefore calculate the Highest Common Factor (H.C.F.)
of (x,c), which by definition is a factor of x.

DEF PROCHhcf
x1 = x
m = x - c*INT(x/c)
WHILE m > 0
	x = c
	c = m
	x = x MOD c
	ENDWHILE
IF c > 1 THEN PRINT "FACTORS = " c " * " x1/c

My HCF method of factoring multiplies
groups of prime factors
  c * (6n-1)*(6n+1)
up to 5000; till as near as possible to 2E9.

It then tests HCF (x,c).
This finds factors up to 5000. ... Reduce to
prime factors by PROCfast  (IF x MOD j = 0).

The factorisation may be completed by using
PROCfast or, if x > 2E9 Then PROCsplit.

ooooooooooo

YES.
BEST NEEDS basic64

 progm--    fin.soc.acorncpusr.donWn994/2.pi.facthcff. byte/zeta4
don mcdonald,    18.07.99  12:30 PM. 16:00. 22:25

Examples : 1E15-1,  1E18/999 999,  2^37-1,  2^31-1
2^33-9 prime,  6763*10627*29947 Maple IsPrime
1E10-1, 1E11-1,  1E12-1, 1E14-1, 2^32+1 Euler, 13^10+1
1E13-1, 1E16-1,  100 895 598 169 Mersenne
10 662 526 601,  15 527 402 881.


factor 5 byte integer, max 2^40  gets most factors .TEST bugs
enter no. / expression  . Qq/ 0 <CR> = quit  ?6763*10627*29947
6763*10627*29947 = 2152302898747

proc Hhcf(x = 2152302898747
  x  > 2 ^31.  slow e.g. minutes.
TRY FOR j = 4999  TO SQRT = 1467072.90164701757  STEP 2.
factors ?   x1 =  j*x1 =   6763 *  318246769
   centiseconds = 1271

 You have 10 seconds to press a key.
6763 prime.        centisec = 2275
10627 * 29947
29947 prime.       centisec = 2762
6763 * 318246769

factor 5 byte integer, max 2^40  gets most factors .TEST bugs
enter no. / expression  . Qq/ 0 <CR> = quit  ?100895598169
100895598169 = 100895598169

proc Hhcf(x = 100895598169
  x  > 2 ^31.  slow e.g. minutes.
TRY FOR j = 4999  TO SQRT = 317640.674613626907  STEP 2.
factors ?   x1 =  j*x1 =   112303 *  898423
   centiseconds = 6846

 You have 10 seconds to press a key.
112303 prime.      centisec = 7862
898423 prime.      centisec = 7906
112303 * 898423

factor 5 byte integer, max 2^40  gets most factors .TEST bugs
enter no. / expression  . Qq/ 0 <CR> = quit  ?1E18/999999
1E18/999999 = 1000001000001

proc Hhcf(x = 1000001000001

 HCF = 57
1000001000001  Factor = 57 * 17543877193
3 * 19
19 prime.          centisec = 7
  x  > 2 ^31.  slow e.g. minutes.
TRY FOR j = 4999  TO SQRT = 132453.301933171897  STEP 2.
factors ?   x1 =  j*x1 =   52579 *  333667
   centiseconds = 3721

 You have 10 seconds to press a key.
52579 prime.       centisec = 4732
333667 prime.      centisec = 4759
52579 * 333667

factor 5 byte integer, max 2^40  gets most factors .TEST bugs
enter no. / expression  . Qq/ 0 <CR> = quit  ?
progm facthcff.   e n d.    CLOSEs * RAM SPOOL
