GCD, Bezout, and Modular Inverses | The Extended Euclidean Algorithm

Подписаться 3 тыс.

Просмотров 6 тыс.

50% 1

In this video, I talk about the Extended Euclidean Algorithm, a method for solving integer equations of the form ax + by = n.
Wikipedia article: en.wikipedia.org/wiki/Extende...
Code: github.com/womogenes/extended...
00:00 Intro
00:34 The gcd function
01:48 The standard Euclidean algorithm
05:28 Implementing the standard Euclidean algorithm
07:22 Extending the Euclidean algorithm
08:08 Worked example
15:14 Generalization
16:40 Implementing the Extended Euclidean Algorithm
18:42 Application - modular inverses
21:16 Summary

Игры

Опубликовано:

21 июл 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 14

@voltflake 2 года назад

Man, your videos are some of the best youtube/internet has about this topic. Thank you so much!

@aiham224 Год назад

I F agree, i have been struggling for days to understand this

@jdhp3696 2 года назад

Thanks for the awesome video.

@januaryjohnson8107 2 года назад

Great video! Thanks so much!!

@tanhnguyen2025 2 месяца назад

very easy to understand.

@Luke-jh5hi 2 года назад

Second semester Computer Science and thanks to you I believe I'll graduate one day 😁

@Lucas-pj9ns Год назад

is there any guarantees on the maximum size of x and y? trying to code this up in c++ and im worried about overflow

@fredpim11 Год назад

great video and explanation maybe something on "the baby step giant step algorythm... on the continuation... thanks for your share

@AlexTurbo 2 года назад

thank you

@thomasyang9517 Год назад

good vid

@skaunov_code Год назад

I guess it doesn't take polynomials into account? Is there a version with them? X)

@TheStephenShu Год назад

I found 77(23)+30(-59)=1. I wonder how to find different solutions

@fredpim11 Год назад

when you get one particular solution you get every other ones: 77a + 30b=1 one solution you get is a=23 and b=-59 here you have to think at this form 77a=1mod 30 and 30b=1mod77 the other solutions of a are mod30 and mod 77 for b a are more or minus 30 and b are more or minus 77 a=-7, b=18 a=23, b=-59 a=-37, b=95 a=53,b=-137 etc...

@Luke-jh5hi 2 года назад

And please make a video about RSA🙏