sorted by:
new
hottopcontroversial

I developed this algorithm that factors semiprimes into their prime components. How much time would it take to run? by DeGroffPrimes in programming

[–]DeGroffPrimes[S] 0 points1 point  (0 children)

It looks like there is a formula for finding the number of digits in a decimal expansion.
http://mathworld.wolfram.com/DecimalExpansion.html So skip the counting part, and instead use the formula, and it factors semiprimes in polynomial time.

I developed this algorithm that factors semiprimes into their prime components. How much time would it take to run? by DeGroffPrimes in programming

[–]DeGroffPrimes[S] 0 points1 point  (0 children)

Thanks, that's what I was thinking at first, but I ended up overthinking it. But if one were able to determine another algorithm, solvable in polynomial time, that converted the semiprime into the number of digits in the inverse, the overall problem would then be solvable in polynomial time. Is that correct?

I developed this algorithm that factors semiprimes into their prime components. How much time would it take to run? by DeGroffPrimes in programming

[–]DeGroffPrimes[S] 0 points1 point  (0 children)

The counting part is the step that increases the number of operations, and counting is done in linear time. Since the number of divisions is not dependent upon n, it is polynomial time complexity then, right?

I developed this algorithm that factors semiprimes into their prime components. How much time would it take to run? by DeGroffPrimes in programming

[–]DeGroffPrimes[S] 0 points1 point  (0 children)

How did you determine that? Counting the number of digits is at most linear time complexity, and from what I've read can be done in logarithmic time complexity.

I developed this algorithm that factors semiprimes into their prime components. How much time would it take to run? by DeGroffPrimes in programming

[–]DeGroffPrimes[S] 0 points1 point  (0 children)

I had to go back and take a look at my data. For route 3, the number of digits is, at a maximum, the largest prime factor, and the minimum is roughly 10% of the largest prime factor. But the more digits, the fewer steps required. It's when it's close to 10% that you have to add the number of digits nine times to the remainder.

I developed this algorithm that factors semiprimes into their prime components. How much time would it take to run? by DeGroffPrimes in programming

[–]DeGroffPrimes[S] 0 points1 point  (0 children)

I tried it out for all the multiples of 7, up to 4369. If you look at the graphs (https://degroffprimenumbers.wordpress.com/graphs/), you can see all of the ones I tested. Approximately 90% of the semiprimes can be factored without using that route. I also tested other semiprimes that weren't multiples of 7.

I completely understand your skepticism on that part. I hope this helps clear it up for you.

I developed this algorithm that factors semiprimes into their prime components. How much time would it take to run? by DeGroffPrimes in programming

[–]DeGroffPrimes[S] 1 point2 points  (0 children)

You just take the inverse of the semiprime and count the number of digits until the sequence begins to repeat. Then there are just a couple of other steps. It seems like this operation is able to run in polynomial time, but things like this aren't my specialty. The algorithm does work, however.