Prime Factoring Algorithm

[R.D. Silverman]

When I am talking about a gradient between 2 rational points I will still be working in Q^2,right?

No, you will be working in never-never land. Continuous functions
have gradients. Points in Q^2 do not.

Two points to clarify here. Firstly I am finding points on a conic section which by itself is not discrete.

You are finding *rational points* on a conic, which is a commutative
algebraic variety and most definitely is discrete,

Secondly and I have repeated this many times I am not using a descent algorithm or an iterative procedure. I will follow m f h's advise and write out a few more examples outlining just the steps. Maybe it will be clearer.

I agree and disagree.All difference of square methods up to now have been iterative and thus exponential.

You just got added to my official list of cranks. This last remark shows
total cluelessness. diff of squares is NOT exponential because it is
iterative. It is exponential because of the SIZE OF THE SEARCH SPACE

Mine as I have said before is not an iterative process. I am trying to round the edges off of the square to make it circular.

OUROBOS. You don't know enough math to even understand that what
you are trying to do CAN'T work unless P=NP.

Do you even know what exclusion moduli are?

[retina]

I found a proof that P=NP, and I would have posted it here but the margin is not big enough.

[Visu]

Originally Posted by R.D. Silverman

You just got added to my official list of cranks.

Thanks. That's the best complement I have gotten all year.

[Visu]

[QUOTE=R.D. Silverman;132912]

You just got added to my official list of cranks. This last remark shows
total cluelessness. diff of squares is NOT exponential because it is
iterative. It is exponential because of the SIZE OF THE SEARCH SPACE

[QUOTE]

Always thought the METHOD of searching is more important than the SIZE OF THE SEARCH SPACE. Of course what does a clueless crank know.

[Visu]

Originally Posted by R.D. Silverman

You just got added to my official list of cranks. This last remark shows
total cluelessness. diff of squares is NOT exponential because it is
iterative. It is exponential because of the SIZE OF THE SEARCH SPACE

Always thought the METHOD of searching is more important than the SIZE OF THE SEARCH SPACE. Of course what does a clueless crank know.

[masser]

Apparently, not much.

Plonk.

[xilman]

Originally Posted by R.D. Silverman

You just got added to my official list of cranks. This last remark shows total cluelessness. diff of squares is NOT exponential because it is
iterative. It is exponential because of the SIZE OF THE SEARCH SPACE

I observe that both QS and NFS have as their aim to represent N as a (non-trivial) difference of two squares.

Not entirely sure I should have posted this observation for fear of casting confusion rather than enlightenment, but what the hell

Paul

[R.D. Silverman]

Originally Posted by xilman

I observe that both QS and NFS have as their aim to represent N as a (non-trivial) difference of two squares.

Not entirely sure I should have posted this observation for fear of casting confusion rather than enlightenment, but what the hell

Paul

No. They do not. They represent some *undetermined multiple of N*
as the difference of two squares.

[xilman]

Originally Posted by R.D. Silverman

No. They do not. They represent some *undetermined multiple of N*
as the difference of two squares.

Which is ripped out by the final GCD which forms the last stage of the algorithms.

I know, I know, I'm just being mischievous. 8-)

Paul

[Visu]

Originally Posted by R.D. Silverman

You just got added to my official list of cranks. This last remark shows
total cluelessness. diff of squares is NOT exponential because it is
iterative. It is exponential because of the SIZE OF THE SEARCH SPACE

Read and reread this statement and I am still confused. I always thought that an algorithm is exponential ( or polynomial or linear) REGARDLESS of the size of the search space not because of it. And that your search space is defined by your problem and not your algorithm.

[R.D. Silverman]

Originally Posted by Visu

Read and reread this statement and I am still confused. I always thought that an algorithm is exponential ( or polynomial or linear) REGARDLESS of the size of the search space not because of it. And that your search space is defined by your problem and not your algorithm.

Have you ever tried reading a BOOK on the subject?
Aho, Hopcroft, & Ullman is a good start. Garey & Johnson is excellent.

Consider LP. A node traversing method such as Simplex is strictly
exponential because the number of nodes is exponential in the size of the
problem. Klee & Minty showed that any method for choosing a new basis
variable at each step can require traversing ALL the nodes.
However, modern LP codes rescale problems in a way that tends to
destroy artificial problems such as Klee & Minty's so that Simplex
works well in practice. (But it is still worst case exponential)

OTOH, Khachian's algorithm is polynomial time, even though the search
space (the volume of the feasible region) is exponential in the size of
the problem. The size of the search space is determined by the problem.
But a clever algorithm can reduce an exponential search space by a fixed
fraction at each iteration and hence solve an exponentially sized problem
in polynomial time.

An interior point method also chops off a fixed fraction of the remaining
search space at each iteration.

Difference of squares methods are strictly exponential precisely because
the abelian variety that is being search is really a scheme.
(Think of it as a function space where the elements of the space are
really just the rings you are trying to separate)

There is no canonical ordering of points that makes one solution to N = pq where
p,q, are RATIONAL any "better" than any other. Lacking such a metric,
there is no way that any kind of algorithm that searches lattice points
can determine the "best" direction to move when moving from one point
to another. The worst case is that it must search exponentially many
points to pass from a RATIONAL solution to Z.



**IF** we had lattice basis reduction methods that could guarantee to
reduce a basis
vector by a fixed fraction at each iteration, we would have a poly-time
factoring algorithm. But the "shortest-vector" problem is NP-Complete.
LLL can reduce a basis vector somewhat, but it is not guaranteed to
reduce it by a fixed fraction.