0
|
340 Views
|
3 Replies
|
3 Total Likes
View groups...
Share
GROUPS:

# Algorithm taking longer than expected to evaluate

Posted 22 days ago
 p=2564855351 For[i = 3, i <= p, i+2, If[(Sqrt[p^3/(p*i^2+i)] - p) < 0.5, x = i, Print[i], i=p+1 ] ] While[x<= p, x+2 If[ Divisible[p,x], Print[x], p = 1]; ]  This should factor a large semi-Prime number fast. But the computation never ends. I thought it would be faster than plain division. Yes, I know fast methods exist. I just wanted to get this to work.
3 Replies
Sort By:
Posted 21 days ago Thanks for testing the code and also improving it.I know it seems more complex method than other algorithms. But the (Sqrt[p^3/(p*i^2 + i)] - p) < 0.5 equation is to be graphed and once graphed the lower semiprime should have a y value of zero.I call it the Pappy Craylar conjecture. I used 0.5 because with different Prime factors there is sometimes an error. But I would say with even larger semiprimes the zero will occur fairly close to the smaller Prime factor.I have other equations that do the same thing. But my question to you is, “Is it useful? I know it is still difficult to factor semiprimes, but I proposed modifying the PC Method to test for Primility. That is if a known Prime with a test Prime forms a semiprime at zero the number is Prime. I thought we could identify larger Prime numbers.I posted on a science forum the equation could defeat RSA or be a start of looking for patterns in Prime numbers. Obviously, that is more of a wish than a hypothesis, but I still see potential.Thanks for looking at my code. I have been trying to get it to work for years.I have included a picture of my equations and where they meet zero. If you are interested I can explain more.
Posted 22 days ago
 I tried something different. I gave the problem to GPT and asked it to optimise the code. The first time around it gave code that didn't work. The next time the code did appear to do what it is supposed to do. On my computer at least the optimised version is vastly faster than the posted code. Here is the discussion with GPT. So the original code is: p = 2564855351 Monitor[For[i = 3, i <= p, i += 2, If[(Sqrt[p^3/(p*i^2 + i)] - p) < 0.5, x = i, Print[i], i = p + 1]]; While[x <= p, x + 2 If[Divisible[p, x], Print[x], p = 1];], I] The optimised code, which interrupts once it finds the first divisor, is: p = 2564855351; x = 3; Monitor[While[x <= p, If[(Sqrt[p^3/(p*x^2 + x)] - p) < 0.5, Print[x]; Break[];]; x += 2;]; If[x <= p, While[x <= p, If[Divisible[p, x], Print[x]; Break[];]; x += 2;];], x] Which I did not really test, but it gives 41227 If you run the built in Mathematica function Divisors[p] you get {1, 41227, 62213, 2564855351} This suggests that the code performs ok in this case. As you know the number is relatively prime, you can easily divide p/41227 to obtain 62213. I did not analyse the code or look at any other cases in more detail. It would also be possible to parallelise the entire code, which could give you another speed boost. Best wishes, Marco
Posted 22 days ago
 Try For[i = 3, i <= p, i+=2, instead of For[i = 3, i <= p, i+2, and see what that does for youThere may be a similar problem inside your While loop and some of your commas may need to be replaced with semicolons, but I can't be certain of some of those. With trial and error substitutions I was able to get your code to quickly display the smaller prime factor of your semiprime.