Message Boards Message Boards

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

Algorithm taking longer than expected to evaluate

Posted 8 months 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
5 Replies

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 8 months 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

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

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


Monitor[While[x<p, If[(x*(Sqrt[p^3/(p*x^2+x)])-p)<0.5, Print[x];
 If [x <= p, While[x<p, If[Divisible[p,x],
    x +=2;];], x]

Here is the corrected equation. Thanks again for helping me with the programming. Notice it is x * Square root. It is x*y = p.

Did Wolfram do away with the CDF format? I wanted to make this program interactive for those who don’t have Mathematica.

The programming will have to test 100 digit SemiPrimes. Values will have to be tested to find where y equals zero. It should be faster than division, but it still is a computation.

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

Group Abstract Group Abstract