20030807, 00:09  #1 
Sep 2002
2·331 Posts 
Different types of factoring, implementation
Types of factoring, aware of/interested in.
Prime95 style trial factoring to find a small prime factor to save the time of a more extensive prime test. RSA style factoring find 2 large roughly equal size prime factors of a large number. Complete factorization finding all the prime factors of a given number, trial factoring could be a starting point because it can give one of the factors. NSFNET factoring using the NFS to find factors of large numbers usually of a n^p +/ d The code/algorithms behind the factoring efforts is of great interest, for improvement, alternative theories, challenge of reimplementing it to understand the subtle issues of the algorithm. 
20030807, 01:11  #2 
10010001100010_{2} Posts 
Factors of remainders.
Mp is prime if it divides S(p2) with S(0)=4. true
Mp is prime if it divides S(p2) with S(0)=3, and p=3(mod4). true Although it works with p=1(mod 4) up to 4500, but is not nessesarily true. So, is Mp is probably prime if it divides the remainder R of : [S(p2) with S(0)=4] = R (mod [S(p2) with S(0)=3] ) This has got to be faster than the current procedure at least when p=3(mod 4). Right? It could make for lone p=3(mod4) hunters. :D Edit, I posted this as a new topic, and it came out as a reply... hmmm 
20030807, 04:34  #3  
Aug 2002
Richland, WA
2^{2}×3×11 Posts 
Re: Factors of remainders.
Quote:


20030807, 08:10  #4  
3×11×13^{2} Posts 
Quote:
The remainder between S(0)=3 & S(0)=4 is way smaller. Besides I dont believe that these large numbers are actually divided. The only catch I can think of is that the power algorithm may be different than that of S(0)=4. I'll check that out and repost later. (indeed) BTW S(0)=3 are Lucas(Golden ratio) numbers possesing an index of a power of two. 3 7 47 2207 4870847... *22 *22 *22... 

20030807, 09:02  #5 
May 2003
2^{5}·3 Posts 
Actually, all the S(x) computations are done MOD 2^p  1 . That means that wether you start with 3 or 4, as soon as the square is higher than Mp, you take the MOD, and there's not telling which one will be greater at that point (it will probably alternate), so the multiplication times would not make any difference appart from the first few iterations.
In my opinion, you will get a gain of a few milliseconds on the whole LLTest. 
20030807, 10:03  #6  
Aug 2002
Richland, WA
2^{2}·3·11 Posts 
Re: Factors of remainders.
Quote:
Are you proposing that you we caculate S(p2)  S(0)=3 first and then do S(p2)  S(0)=4 mod that? Or are you suggesting that we calculate [ S(1)  S(0)=4 ] ( mod [ S(1)  S(0)=3 ] ), then [ S(2)  S(0)=4 ] ( mod [ S(2)  S(0)=3 ] ), etc.? 

20030807, 16:53  #7  
Jun 2003
The Texas Hill Country
3^{2}·11^{2} Posts 
Re: Different types of factoring, implementation
Quote:
There is money in this one. "Raising Cash from Accounts Receivable" 

20030807, 19:33  #8 
Sep 2002
2·331 Posts 
Yes,
Factoring in the AR sense, I had never heard of factoring in that sense until a few months ago when searching for factoring algorithms and the AR factoring was filling the search results. I don't think it has much, if any, relation to factoring integers into their prime factors. I prefer prime factorization. :) 
20030807, 19:44  #9 
May 2003
2^{5}·3 Posts 
I'm not 100% sure, but I think Wackerbarth is referring to Factoring Fermat Numbers.
If you ever find a new one of a Fermat number with n between 12 and 22, don't forget to notify Perfectly Scientific Inc. and they will give you money for it. 
20030807, 20:04  #10 
Sep 2002
2×331 Posts 
Factoring algorithms:
Brute force divide by odds ( or primes) <= square root (coded) Trial factoring if bit[i] of p = 1 then *2 algorithm. (coded) P1 factoring. ECM Difference of two squares. (coded) NFS (Number Field Seive) and it's predecessors. Does anybody know of any other factoring algorithms ? Ones that can be coded without needing an advanced understanding of number theory. Any theories that could possibly be made into algorithms/heuristics/rules of thumb ? 
20030807, 20:12  #11  
Aug 2002
2^{6}×5 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
SQUFOF implementation  alpertron  Factoring  15  20100412 19:16 
ECM/FPGA Implementation  rdotson  Hardware  12  20060326 22:58 
need C implementation of divb(r,k)  Leith  Miscellaneous Math  4  20050118 23:14 
RSA implementation  flava  Programming  12  20041026 03:51 
Types of work to request from server : Add P1 Factoring  MoZ  Software  2  20040206 20:24 