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

# Algorithm taking longer than expected to evaluate

Posted 7 months 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.
5 Replies
Sort By:
Posted 4 months ago
 Clear[x,p]; p=2564855351; x=3; Monitor[While[x
Posted 6 months ago
 As I mentioned in a previous thread, I have trouble graphing the equations that find the smaller Prime factor. It is graphable, but the view of the graph can be misleading. I think at negative infinity on the x-axis the graph approaches infinity of the y-axis. Then there is a curve that is in the shape of a parabola as x approaches zero from the left. This curve dips into the negative number. And as x approaches the smaller factor y is moved into positive numbers.To me it looks like an inverted normal distribution.I was going through a book of curves and found 3 curves which might be manipulated to fit these curves of the equations in questioned. It is just a hunch and it would be a challenge to manipulate the curves mathematically so the entire series matched. Do you think it is possible?y = cx^(2) e^(ax^(2))y = tanh^(2) (5x)inverse of normal distribution
Posted 7 months 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 7 months 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 7 months 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.