 mersenneforum.org Different types of factoring, implementation
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read  2003-08-07, 00:09 #1 dsouza123   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 re-implementing it to understand the subtle issues of the algorithm.   2003-08-07, 01:11 #2 TTn   100100011000102 Posts Factors of remainders. Mp is prime if it divides S(p-2) with S(0)=4. true Mp is prime if it divides S(p-2) 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(p-2) with S(0)=4] = R (mod [S(p-2) 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  2003-08-07, 04:34   #3
NickGlover

Aug 2002
Richland, WA

22×3×11 Posts Re: Factors of remainders.

Quote:
 Originally Posted by TTn So, is Mp is probably prime if it divides the remainder R of : [S(p-2) with S(0)=4] = R (mod [S(p-2) 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.
Isn't [S(p-2) with S(0)=3] REALLY big? That would make very large and slow multiplies necessary.   2003-08-07, 08:10   #4
TTn

3×11×132 Posts Quote:
 Isn't [S(p-2) with S(0)=3] REALLY big? That would make very large and slow multiplies necessary.
Not really, it is smaller than S(0)=4
The remainder between S(0)=3 &amp; 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... *2-2 *2-2 *2-2...  2003-08-07, 09:02 #5 Axel Fox   May 2003 25·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 LL-Test.   2003-08-07, 10:03   #6
NickGlover

Aug 2002
Richland, WA

22·3·11 Posts Re: Factors of remainders.

Quote:
 Originally Posted by TTn So, is Mp is probably prime if it divides the remainder R of : [S(p-2) with S(0)=4] = R (mod [S(p-2) with S(0)=3] )
I guess I just don't understand the algorithm you're proposing. I understand how S(p-2) | S(0)=3 works by itself, but I don't think its clear what [ S(p-2) | S(0)=4 ] = R ( mod [ S(p-2) | S(0)=3 ] ) actually implies for the algorithm.

Are you proposing that you we caculate S(p-2) | S(0)=3 first and then do S(p-2) | 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.?   2003-08-07, 16:53   #7
Wacky

Jun 2003
The Texas Hill Country

32·112 Posts Re: Different types of factoring, implementation

Quote:
 Originally Posted by dsouza123 Types of factoring, aware of/interested in. Prime95 ... ... NSFNET factoring ...
You left out a major one.
There is money in this one.

"Raising Cash from Accounts Receivable"   2003-08-07, 19:33 #8 dsouza123   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. :)   2003-08-07, 19:44 #9 Axel Fox   May 2003 25·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.   2003-08-07, 20:04 #10 dsouza123   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) P-1 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 ?   2003-08-07, 20:12   #11
ColdFury

Aug 2002

26×5 Posts Quote:
 Ones that can be coded without needing an advanced understanding of number theory.
You can code the Quadratic Sieve without much understanding of "why" it works.   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post alpertron Factoring 15 2010-04-12 19:16 rdotson Hardware 12 2006-03-26 22:58 Leith Miscellaneous Math 4 2005-01-18 23:14 flava Programming 12 2004-10-26 03:51 MoZ Software 2 2004-02-06 20:24

All times are UTC. The time now is 23:39.

Sun Apr 18 23:39:47 UTC 2021 up 10 days, 18:20, 0 users, load averages: 2.54, 2.36, 2.04

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.