Extended Euclidean algorithm - Revision history

Rational Point: /* Using GNU multiprecision bignum classes */ spell out words & skip the branding

2024-12-23T06:57:01Z

Using GNU multiprecision bignum classes: spell out words & skip the branding

← Older revision		Revision as of 06:57, 23 December 2024
Line 47:		Line 47:
	</syntaxhighlight>		</syntaxhighlight>

	== Using ~~GNU multiprecision bignum~~ classes ==		== Using multiple precision big number classes ==

	The <tt>long int</tt> primitive type in C++ cannot handle numbers bigger than 18,446,744,073,709,551,615 on most computers.		The <tt>long int</tt> primitive data type in C++ cannot handle numbers bigger than 18,446,744,073,709,551,615 on most computers.
	The program above may be adapted to handle much, much bigger numbers with ~~multiprecision~~ arithmetic, and this is practical for actual implementations that will be highly efficient. Be sure <tt>g++</tt>, <tt>gmp</tt>, <tt>gmp++</tt>, <tt>gmp-devel</tt> are installed on your your Fedora Linux system, e.g.		The program above may be adapted to handle much, much bigger numbers with multiple precision arithmetic, and this is practical for actual implementations that will be highly efficient. Be sure <tt>g++</tt>, <tt>gmp</tt>, <tt>gmp++</tt>, <tt>gmp-devel</tt> are installed on your your Fedora Linux system, e.g.
	<syntaxhighlight lang="bash">		<syntaxhighlight lang="bash">
	$ sudo dnf install gmp gmp++ gmp-devel		$ sudo dnf install gmp gmp++ gmp-devel
Line 58:		Line 58:
	#include <gmpxx.h>		#include <gmpxx.h>
	</syntaxhighlight>		</syntaxhighlight>
	along with the other includes, declare the variables as <tt>mpz_class</tt> instead of <tt>long int</tt>, and link the ~~bignum~~ libraries when you compile <ref>The GNU Multiple Precision Arithmetic Library. https://gmplib.org/</ref><ref>— , Manual § 12.1 C++ Interface General. https://gmplib.org/manual/C_002b_002b-Interface-General</ref>, assuming here you have saved the program as <tt>e-euclid.cpp</tt>.		along with the other includes, declare the variables as <tt>mpz_class</tt> instead of <tt>long int</tt>, and link the GMP Bignum libraries when you compile <ref>The GNU Multiple Precision Arithmetic Library. https://gmplib.org/</ref><ref>— , Manual § 12.1 C++ Interface General. https://gmplib.org/manual/C_002b_002b-Interface-General</ref>, assuming here you have saved the program as <tt>e-euclid.cpp</tt>.
	<syntaxhighlight lang="bash">		<syntaxhighlight lang="bash">
	$ g++ -o e-euclid e-euclid.cpp -lgmpxx -lgmp		$ g++ -o e-euclid e-euclid.cpp -lgmpxx -lgmp
	$ ./e-euclid		$ ./e-euclid
	</syntaxhighlight>		</syntaxhighlight>

Rational Point: with bignum arithmetic

2024-12-23T06:43:14Z

with bignum arithmetic

← Older revision		Revision as of 06:43, 23 December 2024
Line 9:		Line 9:
	Given two positive integers ''a'' and ''b'', this [[Diophantine equation]] is solved for integers ''x, y'', which will not both be positive, and <math>d=\gcd(a,b)</math>.		Given two positive integers ''a'' and ''b'', this [[Diophantine equation]] is solved for integers ''x, y'', which will not both be positive, and <math>d=\gcd(a,b)</math>.

	If <math>d=1</math>, the algorithm yields the [[modular inverse]]s<ref>Bufalo, Michele, Daniele Bufalo, and Giuseppe Orlando. “A Note on the Computation of the Modular Inverse for Cryptography” ''Axioms,'' vol. 10, no. 2(116), 2021. https://www.mdpi.com/2075-1680/10/2/116</ref> of ''a'' mod ''b'' and ''b'' mod ''a'' since in this case the congruences		If <math>d=1</math>, the algorithm yields the [[modular inverse]]s <ref>Bufalo, Michele, Daniele Bufalo, and Giuseppe Orlando. “A Note on the Computation of the Modular Inverse for Cryptography” ''Axioms,'' vol. 10, no. 2(116), 2021. https://www.mdpi.com/2075-1680/10/2/116</ref> of ''a'' mod ''b'' and ''b'' mod ''a'' since in this case the congruences

	:<math>ax\equiv 1 \mod b</math>		:<math>ax\equiv 1 \mod b</math>
Line 15:		Line 15:
	:<math>by \equiv 1\mod a</math>		:<math>by \equiv 1\mod a</math>

	are solved. Here is a naïve C++ implementation of [https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Pseudocode pseudocode found on Wikipedia].		are solved.
			== Example code ==
			Here is a naïve C++ implementation of [https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Pseudocode pseudocode found on Wikipedia].

	<syntaxhighlight lang="cpp" line="">		<syntaxhighlight lang="cpp" line="">
Line 43:		Line 45:
	}		}

			</syntaxhighlight>

			== Using GNU multiprecision bignum classes ==

			The <tt>long int</tt> primitive type in C++ cannot handle numbers bigger than 18,446,744,073,709,551,615 on most computers.
			The program above may be adapted to handle much, much bigger numbers with multiprecision arithmetic, and this is practical for actual implementations that will be highly efficient. Be sure <tt>g++</tt>, <tt>gmp</tt>, <tt>gmp++</tt>, <tt>gmp-devel</tt> are installed on your your Fedora Linux system, e.g.
			<syntaxhighlight lang="bash">
			$ sudo dnf install gmp gmp++ gmp-devel
			</syntaxhighlight>
			Be sure you have
			<syntaxhighlight lang="cpp">
			#include <gmpxx.h>
			</syntaxhighlight>
			along with the other includes, declare the variables as <tt>mpz_class</tt> instead of <tt>long int</tt>, and link the bignum libraries when you compile <ref>The GNU Multiple Precision Arithmetic Library. https://gmplib.org/</ref><ref>— , Manual § 12.1 C++ Interface General. https://gmplib.org/manual/C_002b_002b-Interface-General</ref>, assuming here you have saved the program as <tt>e-euclid.cpp</tt>.
			<syntaxhighlight lang="bash">
			$ g++ -o e-euclid e-euclid.cpp -lgmpxx -lgmp
			$ ./e-euclid
	</syntaxhighlight>		</syntaxhighlight>

Rational Point: simplify proposed title

2024-12-23T05:36:11Z

simplify proposed title

← Older revision		Revision as of 05:36, 23 December 2024
Line 9:		Line 9:
	Given two positive integers ''a'' and ''b'', this [[Diophantine equation]] is solved for integers ''x, y'', which will not both be positive, and <math>d=\gcd(a,b)</math>.		Given two positive integers ''a'' and ''b'', this [[Diophantine equation]] is solved for integers ''x, y'', which will not both be positive, and <math>d=\gcd(a,b)</math>.

	If <math>d=1</math>, the algorithm yields the [[modular ~~multiplicative~~ inverse]]s<ref>Bufalo, Michele, Daniele Bufalo, and Giuseppe Orlando. “A Note on the Computation of the Modular Inverse for Cryptography” ''Axioms,'' vol. 10, no. 2(116), 2021. https://www.mdpi.com/2075-1680/10/2/116</ref> of ''a'' mod ''b'' and ''b'' mod ''a'' since in this case the congruences		If <math>d=1</math>, the algorithm yields the [[modular inverse]]s<ref>Bufalo, Michele, Daniele Bufalo, and Giuseppe Orlando. “A Note on the Computation of the Modular Inverse for Cryptography” ''Axioms,'' vol. 10, no. 2(116), 2021. https://www.mdpi.com/2075-1680/10/2/116</ref> of ''a'' mod ''b'' and ''b'' mod ''a'' since in this case the congruences

	:<math>ax\equiv 1 \mod b</math>		:<math>ax\equiv 1 \mod b</math>

Rational Point: spacing for readability in program

2024-12-20T19:45:08Z

spacing for readability in program

← Older revision		Revision as of 19:45, 20 December 2024
Line 22:		Line 22:

	int main(int argc, char **argv) {		int main(int argc, char **argv) {
	long int a,b,q,r0,r1,r,s0=1,s1,s=0,t0=0,t1,t=1;		long int a, b, q, r0, r1, r,
			s0 = 1, s1, s = 0, t0 = 0, t1, t = 1;
	std::cout << "Enter two positive integers: ";		std::cout << "Enter two positive integers: ";
	std::cin >> a >> b;		std::cin >> a >> b;
	assert(a > 0 && b > 0); r0=a; r=b;		assert(a > 0 && b > 0); r0=a; r=b;
	while(r>0) {		while(r != 0) {
	q=r0/r;		q = r0 / r;
	r1=r0-q*r; r0=r; r=r1;		r1 = r0 - q * r; r0 = r; r = r1;
	s1=s0-q*s; s0=s; s=s1;		s1 = s0 - q * s; s0 = s; s = s1;
	t1=t0-q*t; t0=t; t=t1;		t1 = t0 - q * t; t0 = t; t = t1;
	}		}
	std::cout		std::cout

Rational Point: example program

2024-12-20T19:31:48Z

example program

← Older revision		Revision as of 19:31, 20 December 2024
Line 17:		Line 17:
	are solved. Here is a naïve C++ implementation of [https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Pseudocode pseudocode found on Wikipedia].		are solved. Here is a naïve C++ implementation of [https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Pseudocode pseudocode found on Wikipedia].

	<syntaxhighlight lang="cpp" line>		<syntaxhighlight lang="cpp" line="">
	#include <iostream>		#include <iostream>
	#include <cassert>		#include <cassert>
Line 23:		Line 23:
	int main(int argc, char **argv) {		int main(int argc, char **argv) {
	long int a,b,q,r0,r1,r,s0=1,s1,s=0,t0=0,t1,t=1;		long int a,b,q,r0,r1,r,s0=1,s1,s=0,t0=0,t1,t=1;
	std::cout << "Enter two integers: ";		std::cout << "Enter two positive integers: ";
	std::cin >> a >> b;		std::cin >> a >> b;
	assert(a > 0 && b > 0); r0=a; r=b;		assert(a > 0 && b > 0); r0=a; r=b;

Rational Point: technically, a denominator is a divisor, but ??

2024-12-20T19:22:42Z

technically, a denominator is a divisor, but ??

← Older revision		Revision as of 19:22, 20 December 2024
Line 3:		Line 3:
	[[Category:Number theory]]		[[Category:Number theory]]

	The objective of the '''extended Euclidean algorithm''' is to compute the greatest common ~~denominator~~ of two natural numbers and solve [[Bézout’s identity]]		The objective of the '''extended Euclidean algorithm''' is to compute the greatest common divisor of two natural numbers and solve [[Bézout’s identity]]

	:<math>ax+by=d</math>.		:<math>ax+by=d</math>.

Rational Point: cat, ref

2024-12-20T19:16:34Z

cat, ref

← Older revision		Revision as of 19:16, 20 December 2024
Line 1:		Line 1:
	The objective of the '''~~Extended~~ Euclidean algorithm''' is to compute the greatest common denominator of two natural numbers and solve ~~the~~ [[Diophantine equation]] ~~known as~~ [[~~Bézout’s identity~~]]. Here is a naïve C++ implementation of [https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Pseudocode pseudocode found on Wikipedia].		[[Category:Algorithms]]
			[[Category:C++ programs]]
			[[Category:Number theory]]

			The objective of the '''extended Euclidean algorithm''' is to compute the greatest common denominator of two natural numbers and solve [[Bézout’s identity]]

			:<math>ax+by=d</math>.

			Given two positive integers ''a'' and ''b'', this [[Diophantine equation]] is solved for integers ''x, y'', which will not both be positive, and <math>d=\gcd(a,b)</math>.

			If <math>d=1</math>, the algorithm yields the [[modular multiplicative inverse]]s<ref>Bufalo, Michele, Daniele Bufalo, and Giuseppe Orlando. “A Note on the Computation of the Modular Inverse for Cryptography” ''Axioms,'' vol. 10, no. 2(116), 2021. https://www.mdpi.com/2075-1680/10/2/116</ref> of ''a'' mod ''b'' and ''b'' mod ''a'' since in this case the congruences

			:<math>ax\equiv 1 \mod b</math>
			and
			:<math>by \equiv 1\mod a</math>

			are solved. Here is a naïve C++ implementation of [https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Pseudocode pseudocode found on Wikipedia].

	<syntaxhighlight lang="cpp" line>		<syntaxhighlight lang="cpp" line>
Line 8:		Line 24:
	long int a,b,q,r0,r1,r,s0=1,s1,s=0,t0=0,t1,t=1;		long int a,b,q,r0,r1,r,s0=1,s1,s=0,t0=0,t1,t=1;
	std::cout << "Enter two integers: ";		std::cout << "Enter two integers: ";
	std::cin >> a >> b; assert(a > 0 && b > 0);		std::cin >> a >> b;
	r0=a; r=b;		assert(a > 0 && b > 0); r0=a; r=b;
	while(r>0) {		while(r>0) {
	q=r0/r;		q=r0/r;
Line 17:		Line 33:
	}		}
	std::cout		std::cout
	<< "Bézout coefficients: " << s0 << ", " << t0 << std::endl		<< "Bézout coefficients: "
	<< "greatest common divisor: " << r0 << std::endl		<< s0 << ", " << t0 << std::endl
	<< "quotients by the gcd: " << t << ", "<< s << std::endl;		<< "greatest common divisor: "
			<< r0 << std::endl
			<< "quotients by the gcd: "
			<< t << ", "<< s << std::endl;
	return 0;		return 0;
	}		}

	</syntaxhighlight>		</syntaxhighlight>

Rational Point: pseudocode

2024-12-19T11:52:18Z

pseudocode

New page

The objective of the '''Extended Euclidean algorithm''' is to compute the greatest common denominator of two natural numbers and solve the [[Diophantine equation]] known as [[Bézout’s identity]]. Here is a naïve C++ implementation of [https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Pseudocode pseudocode found on Wikipedia].

<syntaxhighlight lang="cpp" line>
#include <iostream>
#include <cassert>

int main(int argc, char **argv) {
long int a,b,q,r0,r1,r,s0=1,s1,s=0,t0=0,t1,t=1;
std::cout << "Enter two integers: ";
std::cin >> a >> b; assert(a > 0 && b > 0);
r0=a; r=b;
while(r>0) {
q=r0/r;
r1=r0-q*r; r0=r; r=r1;
s1=s0-q*s; s0=s; s=s1;
t1=t0-q*t; t0=t; t=t1;
}
std::cout
<< "Bézout coefficients: " << s0 << ", " << t0 << std::endl
<< "greatest common divisor: " << r0 << std::endl
<< "quotients by the gcd: " << t << ", "<< s << std::endl;

return 0;
}

</syntaxhighlight>