0
$\begingroup$

For most types of quadratic Diophantine equations there exists an algorithm which makes it possible to find a solution (or solutions) over integers (good reference is here: https://www.alpertron.com.ar/METHODS.HTM).

However, those methods require at some stage finding integer divisors of some expression made of equation's coefficients (i.e. A,B,...F). When these are small, then this task is not an issue. However, for coefficients with many digits this becomes an arduous exercise.

Does anyone see a possibility of finding integer solutions of QDE without the need of factorization (i.e. finding integer divisors) along the process?

$\endgroup$
4
  • $\begingroup$ Nothing good in this idea. I like more formalized approach. The basic idea is to bring some form to the binary equivalent. And instead, to solve large - can be reduced to some equivalent to the Pell equation. Such a problem always comes down to the Pell equation. Interest is finding the beautiful connection binary form with equation Pell. Here as you know don't want to lead the discussion. Here is the promotion of your site. $\endgroup$
    – individ
    Mar 30, 2016 at 14:35
  • $\begingroup$ That is not my site individ. Could you please elaborate further on this? $\endgroup$
    – plktrautman
    Mar 30, 2016 at 21:01
  • $\begingroup$ There are several approaches and options. For example one of them can be. artofproblemsolving.com/community/c3046h1048219 You can do another record. The meaning is always the same, be reduced to a simpler equation Pell. $\endgroup$
    – individ
    Mar 31, 2016 at 4:27
  • $\begingroup$ @individ -- see math.stackexchange.com/questions/1721471/… -- a separate entry to elaborate further on Pell's. Please use it if you have time and will. $\endgroup$
    – plktrautman
    Mar 31, 2016 at 8:12

1 Answer 1

Reset to default
1
$\begingroup$

Probably there is no method easier than the method Dario Alpern presents.

Note that in general it is UNDECIDABLE, whether a given polynomial with integer coefficients has integer roots.

The case with $2$ variables and degree $2$ is completely solveable, but you already need some effort to do this.

You can write a program, for example, in PARI/GP. It can easily handle large numbers, and it can factor numbers upto about $60$ digits very fast. PARI/GP supports ECM and quadratic sieve methods. Of course, for $500-600$ digits, some luck is needed to get a factorization in a reasonable time. But checking whether a number is prime is routine even for $500-600$ digit numbers.

As fas as I know, you have to program the methods yourself, PARI/GP does not have a command solving quadratic equations.

$\endgroup$
8
  • $\begingroup$ Thanks. I know it's solveable, but for coefficients of say, 500-600 digits you would need a mainframe to compute this in a reasonable timespan (even though the coefficient expression to factorize is not as hard as for instance RSA numbers, but still -- they may include longish primes, absurdly hard to find on a regular PC). Therefore the only option (apart from using a quantum computer and Shor's algorithm -- well, no thanks) is to find a new method based on pure math. Maybe we're still missing something from these QDEs, we do not see something. $\endgroup$
    – plktrautman
    Mar 30, 2016 at 11:57
  • $\begingroup$ If you use a program like PARI/GP, large numbers are no problem. And with some luck, it can factor even $500-600$ digit-numbers fast. But I am pretty sure, we need the factorization of some number in some cases. $\endgroup$
    – Peter
    Mar 30, 2016 at 12:00
  • $\begingroup$ Seriously? What kind of factoring algorithms does it implement? GNFS? ECM? Could you please elaborate more in a regular response please, so that I can upvote it? :) $\endgroup$
    – plktrautman
    Mar 30, 2016 at 12:03
  • 1
    $\begingroup$ I know :) That is why I am researching this. $\endgroup$
    – plktrautman
    Mar 30, 2016 at 12:04
  • 1
    $\begingroup$ OK, I will keep it secret :) $\endgroup$
    – Peter
    Mar 30, 2016 at 12:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .