Message Boards Message Boards

3 Replies
3 Total Likes
View groups...
Share this post:

Algorithm taking longer than expected to evaluate

Posted 22 days ago

For[i = 3, i <= p, i+2,
If[(Sqrt[p^3/(p*i^2+i)] - p) < 0.5,
x = i,
While[x<=  p, x+2

If[ Divisible[p,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.

POSTED BY: Bobby Joe Snyder
3 Replies

2 Equations of the Pappy Craylar Method

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 BY: Bobby Joe Snyder

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];
  x += 2;];
 If[x <= p, While[x <= p, If[Divisible[p, x], Print[x];
    x += 2;];], x]

Which I did not really test, but it gives


If you run the built in Mathematica function


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 BY: Marco Thiel
Posted 22 days ago


For[i = 3, i <= p, i+=2,

instead of

For[i = 3, i <= p, i+2,

and see what that does for you

There 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.

POSTED BY: Bill Nelson
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
or Discard

Group Abstract Group Abstract