Cornachia’s algorithm can be adapted to the case of the equation x2+dy2=nand even to the case of ax2+bxy+cy2=n. For the sake of completeness, we have given modalities without proofs (the proof in the case of the equa...Cornachia’s algorithm can be adapted to the case of the equation x2+dy2=nand even to the case of ax2+bxy+cy2=n. For the sake of completeness, we have given modalities without proofs (the proof in the case of the equation x2+y2=n). Starting from a quadratic form with two variables f(x,y)=ax2+bxy+cy2and n an integer. We have shown that a primitive positive solution (u,v)of the equation f(x,y)=nis admissible if it is obtained in the following way: we take α modulo n such that f(α,1)≡0modn, u is the first of the remainders of Euclid’s algorithm associated with n and α that is less than 4cn/| D |) (possibly α itself) and the equation f(x,y)=n. has an integer solution u in y. At the end of our work, it also appears that the Cornacchia algorithm is good for the form n=ax2+bxy+cy2if all the primitive positive integer solutions of the equation f(x,y)=nare admissible, i.e. computable by the algorithmic process.展开更多
Luo et al wrote in a recent paper [A Fast Algorithm for Computing gcd Based on Binary Multi Precision,this journal,2002,Vol.32,No.5,pp.542 545; MR 2003h:11161 ] that “the classical Euclid’s algorithm for computing t...Luo et al wrote in a recent paper [A Fast Algorithm for Computing gcd Based on Binary Multi Precision,this journal,2002,Vol.32,No.5,pp.542 545; MR 2003h:11161 ] that “the classical Euclid’s algorithm for computing the gcd of two integers takes time O(\%ln\% 3N)”, and “present” an improved algorithm (called “binary gcd” for short) based on binary multi precision with time complexity O(\%ln\% 2N). In this paper,we point out two well known facts: firstly,the binary gcd,without usefull implimentation improvements, is identical in mathematical theory to Stein’s Binary GCD algorithm published in 1967; secondly,both Euclid’s algorithm and Binary GCD have the same time complexity O(\%ln\% 2N).展开更多
基金Supported by the Science and Technology Project Affiliated to the Education Department of Chongqing Municipality(KJ15012004)Scientific Research Innovation Team Project Affiliated to Yangtze Normal University(2016XJTD01)Science and Technology Plan Projects of Fuling Grant(FLKJ2015ABA1031)
摘要Cornachia’s algorithm can be adapted to the case of the equation x2+dy2=nand even to the case of ax2+bxy+cy2=n. For the sake of completeness, we have given modalities without proofs (the proof in the case of the equation x2+y2=n). Starting from a quadratic form with two variables f(x,y)=ax2+bxy+cy2and n an integer. We have shown that a primitive positive solution (u,v)of the equation f(x,y)=nis admissible if it is obtained in the following way: we take α modulo n such that f(α,1)≡0modn, u is the first of the remainders of Euclid’s algorithm associated with n and α that is less than 4cn/| D |) (possibly α itself) and the equation f(x,y)=n. has an integer solution u in y. At the end of our work, it also appears that the Cornacchia algorithm is good for the form n=ax2+bxy+cy2if all the primitive positive integer solutions of the equation f(x,y)=nare admissible, i.e. computable by the algorithmic process.
摘要Luo et al wrote in a recent paper [A Fast Algorithm for Computing gcd Based on Binary Multi Precision,this journal,2002,Vol.32,No.5,pp.542 545; MR 2003h:11161 ] that “the classical Euclid’s algorithm for computing the gcd of two integers takes time O(\%ln\% 3N)”, and “present” an improved algorithm (called “binary gcd” for short) based on binary multi precision with time complexity O(\%ln\% 2N). In this paper,we point out two well known facts: firstly,the binary gcd,without usefull implimentation improvements, is identical in mathematical theory to Stein’s Binary GCD algorithm published in 1967; secondly,both Euclid’s algorithm and Binary GCD have the same time complexity O(\%ln\% 2N).