mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2010-05-23, 11:35   #67
Merfighters
 
Merfighters's Avatar
 
Mar 2010
On front of my laptop

7×17 Posts
Default A bug?

When I enter a factor during a Rabin-Miller PRP test, then the applet will search for perfect power for a long time, and it will say the factorization is complete.

I tried Phi(9816,10)*Phi(24,10). The applet found the factor 9817 easily, and I entered 1059411433 as a factor(the known factor), then the applet searched for perfect power for a long time, and it said the factorization is complete.
It says that Phi(9816,10)*Phi(24,10) = 9817*1059411433*(a large prime cofactor). But that cofactor is certainly not a prime. It has a prime factor: Phi(24,10) = 99990001.
It is certainly a bug.
Merfighters is offline   Reply With Quote
Old 2010-08-20, 16:49   #68
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

5,857 Posts
Default

I think I have found a bug in the applet. When I enter x=447213595500007;x=x-1;i-21;(x*x-200000000000034400000000000999) in the box at the bottom it produces some negative numbers as well as positive numbers. The positive numbers are factored correctly but the negative numbers aren't. I realize that factorizing negative numbers wasn't really your plan but it would be helpful sometimes if it was fixed although a factor of -1 would need to be added. When I found this I was searching for a suspected bug in my quadratic sieve program.
henryzz is offline   Reply With Quote
Old 2010-08-20, 17:43   #69
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

22·337 Posts
Default

Quote:
Originally Posted by henryzz View Post
I realize that factorizing negative numbers wasn't really your plan but it would be helpful sometimes if it was fixed although a factor of -1 would need to be added.
I'm busy with "real life" now but I will change the applet as soon as possible in order to add this request.
alpertron is offline   Reply With Quote
Old 2010-08-20, 20:11   #70
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

585710 Posts
Default

Quote:
Originally Posted by alpertron View Post
I'm busy with "real life" now but I will change the applet as soon as possible in order to add this request.
Brilliant thanks.
henryzz is offline   Reply With Quote
Old 2010-08-21, 06:45   #71
S485122
 
S485122's Avatar
 
Sep 2006
Brussels, Belgium

22·5·83 Posts
Default

Quote:
Originally Posted by henryzz View Post
I realize that factorizing negative numbers wasn't really your plan but it would be helpful sometimes if it was fixed although a factor of -1 would need to be added.
Nitpicking : Adding unity factors (even negative) is not a good idea. It would be better if the number is negative to output a minus in front of the result : -6 = - (2 * 3) Otherwise there is no reason not to add pairs of -1 factors to any positive number to be factored... You only have a unique factorisation if the input number is positive, which is why the applet currently gives "Number too low (less than 2)." as answer when you try to factor negative numbers ... except when you use a loop (and that is the real bug ;-)

Jacob
S485122 is offline   Reply With Quote
Old 2010-08-21, 08:27   #72
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2×5,323 Posts
Default

Quote:
Originally Posted by S485122 View Post
Nitpicking : Adding unity factors (even negative) is not a good idea. It would be better if the number is negative to output a minus in front of the result : -6 = - (2 * 3) Otherwise there is no reason not to add pairs of -1 factors to any positive number to be factored... You only have a unique factorisation if the input number is positive, which is why the applet currently gives "Number too low (less than 2)." as answer when you try to factor negative numbers ... except when you use a loop (and that is the real bug ;-)

Jacob
Nit-picking: unique factorization is usually interpreted as "unique up to ordering of factors and the presence of units". Personally, I'd not store negative integers in the DB at all.


Paul
xilman is offline   Reply With Quote
Old 2010-08-23, 02:25   #73
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

22·337 Posts
Default

Quote:
Originally Posted by henryzz View Post
I think I have found a bug in the applet. When I enter x=447213595500007;x=x-1;i-21;(x*x-200000000000034400000000000999) in the box at the bottom it produces some negative numbers as well as positive numbers. The positive numbers are factored correctly but the negative numbers aren't. I realize that factorizing negative numbers wasn't really your plan but it would be helpful sometimes if it was fixed although a factor of -1 would need to be added. When I found this I was searching for a suspected bug in my quadratic sieve program.
I think it is ready now. I also changed some parts of the code in order to require less memory by using arrays of integers instead of arrays of longs (32-bit instead of 64-bit data). Please let me know if you find any error.
alpertron is offline   Reply With Quote
Old 2010-08-23, 09:02   #74
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

5,857 Posts
Default

Quote:
Originally Posted by alpertron View Post
I think it is ready now. I also changed some parts of the code in order to require less memory by using arrays of integers instead of arrays of longs (32-bit instead of 64-bit data). Please let me know if you find any error.
Seems to be working thanks.
henryzz is offline   Reply With Quote
Old 2010-09-05, 17:05   #75
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

101 Posts
Default

I did some timings for different JDK or Java compilers.
Times in sec.

jdk 6_21 .588 -> 100%
jdk 7b108 .591 -> 100%
jdk 6_16 .61 -> 104%
jrokit4.0.1 .974 -> 166%
jet7.2 .455 -> 77%

Windows XP
Intel dual core T9400 2.53 Ghz 32 bit
Jet is a Java compiler like gcj. I tried gcj some years ago on windows with cygwin, but had to fight to get an executable (on Windows).
http://www.excelsior-usa.com/downloa...tdlevalaw.html
http://dlc.sun.com.edgesuite.net/jdk...ies/index.html

Last fiddled with by ThiloHarich on 2010-09-05 at 17:05
ThiloHarich is offline   Reply With Quote
Old 2010-09-17, 12:27   #76
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

22·337 Posts
Default New ECM record when running the applet

Robert J DuChateau was running ECM using the applet on 24+29^81 and found the factorization:

347 x 34503928686970842350938851377044353167566697578436905273
(Curve 210438) x
2377058158103859925326651218033244145946260234462377898431463

So he found a 56-digit factor using the applet (a new record). Of course this could have been found faster with SIQS or GNFS (the latter is not implemented in the applet and it will never be done).
alpertron is offline   Reply With Quote
Old 2010-09-17, 13:25   #77
warut
 
Dec 2009

89 Posts
Default

And fastest with SNFS.
warut is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Java applet alternative a1call Programming 19 2019-11-08 22:31
New online applet for factorization ET_ Lone Mersenne Hunters 69 2014-06-01 17:34
A strange applet: 3.14159 Miscellaneous Math 7 2010-06-01 01:29
Faster factorization applet alpertron Factoring 14 2006-01-01 04:00
Binomial Expansion Applet jinydu Lounge 2 2004-05-05 08:33

All times are UTC. The time now is 16:26.

Sat Apr 17 16:26:18 UTC 2021 up 9 days, 11:07, 0 users, load averages: 1.26, 1.56, 1.59

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.