|
|
|
Расширенный алгоритм Евклида с вычитанием
|
|||
|---|---|---|---|
|
#18+
в простых случаях (задачи вида a*b+c*d=1, известны a, c, 1) щелкает как орешки. но сколько ни рытался, задачу с вычитанием не берет a*b-c*d==1 4 8 15 16 23 42 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.09.2008, 15:34 |
|
||
|
Расширенный алгоритм Евклида с вычитанием
|
|||
|---|---|---|---|
|
#18+
А не возникало мыслей, что задача имеет бесконечное количество решений? Например, а=1, с=1 b=2 d=1 b=3 d=2 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.09.2008, 16:12 |
|
||
|
Расширенный алгоритм Евклида с вычитанием
|
|||
|---|---|---|---|
|
#18+
вы чего робяты.. в результате работы алгоритма евклида - b,d - целые числа что блин значит с вычитанием?? если хочешь чтоб d было только отрицательным то всегда могешь вычесть из полученнога числа что нибудь кратное a пока оно не станет отрицательным. ab + cd = 1 , если (d <0) - return если (d >0) d = qa - r ab + c(qa - r) = 1 a(b+cq) - r*c = 1 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.09.2008, 09:05 |
|
||
|
Расширенный алгоритм Евклида с вычитанием
|
|||
|---|---|---|---|
|
#18+
zloy denА не возникало мыслей, что задача имеет бесконечное количество решений? Например, а=1, с=1 b=2 d=1 b=3 d=2 мне нужно хотя бы одно на самом деле, если a и c взаимно просты (куча алгоритмов сюда лезет, например монгомери и рса), то решение только одно ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.09.2008, 11:46 |
|
||
|
Расширенный алгоритм Евклида с вычитанием
|
|||
|---|---|---|---|
|
#18+
Aklin J Прочитай хоть что-нить на эту тему если сам не помнишь. помоему у тебя куча-мала в голове какая-то :-) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.09.2008, 09:44 |
|
||
|
Расширенный алгоритм Евклида с вычитанием
|
|||
|---|---|---|---|
|
#18+
Расширеный алгоритм евклида решает задачу a*b+c*d= НОД(a,c). Если a и c взаимно просты то из неё получается a*b+c*d = 1. решение естессна не одно. если они не взаимно просты то решения не существует. каким макаром ты привязал сюда rsa - не вкуриваю )) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.09.2008, 09:48 |
|
||
|
|
start [/forum/topic.php?fid=16&msg=35521601&tid=1345037]: |
0ms |
get settings: |
10ms |
get forum list: |
20ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
201ms |
get topic data: |
11ms |
get forum data: |
3ms |
get page messages: |
59ms |
get tp. blocked users: |
2ms |
| others: | 253ms |
| total: | 567ms |
| 0 / 0 |
