Форум программистов, компьютерный форум CyberForum.ru

Мультипликативно обратный элемент - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.74
MaXiDRoM_90
10 / 10 / 1
Регистрация: 21.03.2010
Сообщений: 47
07.06.2011, 19:43     Мультипликативно обратный элемент #1
Есть какой-то элемент unsigned __int64 a;
нужно найти к нему мультипликативный обратный по модулю 2^64,т.е. такой x, что a*x=1(mod2^64).
Если пытаться решить это сравнение через алгоритм Евклида,то упираемся в проблему = 2^64 это 65 бит =(

Как найти мультипликативно обратный к a?

Добавлено через 31 минуту
нашёл код для int,его можно переделать под unsigned __int64

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int gcd (int a, int b, int & x, int & y) {
    if (a == 0) {
        x = 0; y = 1;
        return b;
    }
    int x1, y1;
    int d = gcd (b%a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return d;
}
 
 
void main()
{
    int a;
    int m;
 
    int x, y;
    int g = gcd (a, m, x, y);
    if (g != 1)
    cout << "no solution";
    else
    cout << x;
    
    getch();
}
но вот как быть с 2^64

Добавлено через 14 минут
сделал через функцию эйлера - все спасибо
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.06.2011, 19:43     Мультипликативно обратный элемент
Посмотрите здесь:

Обратный порядок C++
Обратный порядок.. C++
Обратный обход C++
C++ Обратный корень
Строки. Как найти в слове первый элемент? Второй элемент, последний элемент? C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
07.06.2011, 19:44     Мультипликативно обратный элемент #2
А можно код показать?
MaXiDRoM_90
10 / 10 / 1
Регистрация: 21.03.2010
Сообщений: 47
07.06.2011, 19:56  [ТС]     Мультипликативно обратный элемент #3
grizlik78, сейчас дописываю,будет через мгновение)

Добавлено через 11 минут
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
unsigned __int64 a;
    unsigned __int64 m=1;  //МОДУЛЬ
 
    /*нужно найти мульт.обр. по модулю 2^64,фи(2^64)=2^63 
    
    обратимы все нечетные числа,поэтому нужно проверить на четность,т.е. последний бит в записи числа*/
 
    int i;
    i=a;
    
    i=i&1;
    if(i==0)
    {
        cout<<"Neobratim\n";
        getch();
        return 0;
    }
    
    m<<=63;     //два в шестдесят третьей
    m=m-1;
 
    unsigned __int64 c=1;
    for(unsigned __int64 i=0;i<m;i++)
    {
        c=c*a;
    }
    cout<<c;
    
    getch();
    return 0;
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
07.06.2011, 20:04     Мультипликативно обратный элемент #4
C++
1
2
3
        unsigned __int64 m=1;  //МОДУЛЬ
 
        m<<=62;         //два в шестдесят третьей
Боюсь что комментарий не соответствует числу. Там 2 в 62-й
Я правильно понимаю, что там огромное количество умножений?
MaXiDRoM_90
10 / 10 / 1
Регистрация: 21.03.2010
Сообщений: 47
07.06.2011, 20:13  [ТС]     Мультипликативно обратный элемент #5
Цитата Сообщение от grizlik78 Посмотреть сообщение
C++
1
2
3
        unsigned __int64 m=1;  //МОДУЛЬ
 
        m<<=62;         //два в шестдесят третьей
Боюсь что комментарий не соответствует числу. Там 2 в 62-й
Я правильно понимаю, что там огромное количество умножений?
да,я уже исправил,сдвиг на 63.
колличество умножений не то что огромное,я даже не знаю сколько цифр в этом числе))
ну а что делать,пока другого алгоритма не придумал

Добавлено через 6 минут
сделал вместо умножений бинарное возведение в степень,считает за секунды
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
07.06.2011, 20:51     Мультипликативно обратный элемент #6
Модифицировал алгоритм Евклида для данного конкретного модуля. Хотя возведение в степень может оказаться эффективнее. В общем спасибо за идею.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <stdint.h>
 
using namespace std;
 
uint64_t inverse_2_64(uint64_t x)
{
    if ( x < 2 )
        return x;
    uint64_t q = uint64_t(0 - x)/x + 1;
    uint64_t u1 = x;
    uint64_t u2 = 1;
    uint64_t v1 = (uint64_t)0 - q * x;
    uint64_t v2 = (uint64_t)0 - q;
    while (v1 != 0)
    {
        uint64_t q = u1 / v1;
        uint64_t t1 = u1 - q*v1;
        uint64_t t2 = u2 - q*v2;
        u1 = v1;
        u2 = v2;
        v1 = t1;
        v2 = t2;
    }
 
    return u1 == 1 ? u2 : 0;
}
 
int main()
{
    uint64_t a = 3;
    uint64_t b = inverse_2_64(a);
    if (b) {
        cout << a << "*" << b << "= 1 (mod 2**64)" << endl;
        cout << "direct multiplication: " << a * b << endl;
    }
    else
        cout << "'a' must be odd number" << endl;
    return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.06.2011, 20:53     Мультипликативно обратный элемент
Еще ссылки по теме:

Если у диагонали этой матрицы находится обратный элемент , то матрицу транспонировать C++
Обратный корень C++
Обратный код C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
MaXiDRoM_90
10 / 10 / 1
Регистрация: 21.03.2010
Сообщений: 47
07.06.2011, 20:53  [ТС]     Мультипликативно обратный элемент #7
Вот что у меня получилось:

#include <iostream>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <ctime>

using namespace std;

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
unsigned __int64 binpow (unsigned __int64 a, unsigned __int64 n) 
{
    if (n == 0)
        return 1;
    if (n % 2 == 1)
        return binpow (a, n-1) * a;
    else {
        unsigned __int64 b = binpow (a, n/2);
        return b * b;
    }
}
 
int main()
{
    unsigned __int64 a=123123;
    unsigned __int64 m=1;  //МОДУЛЬ
 
    /*нужно найти мульт.обр. по модулю 2^64,фи(2^64)=2^63 
    
    обратимы все нечетные числа,поэтому нужно проверить на четность,т.е. последний бит в записи числа*/
 
    int i;
    i=a;
    
    i=i&1;
    if(i==0)
    {
        cout<<"Neobratim\n";
        getch();
        return 0;
    }
    
    m<<=63;     //два в шестдесят третьей
    m=m-1;
    clock_t start=clock();
    unsigned __int64 c=binpow(a,m);
    /*for(unsigned __int64 i=0;i<m;i++)
    {
        c=c*a;
    }*/
    clock_t finish=clock();
    double workTime=(double)(finish - start) / CLOCKS_PER_SEC;
 
    cout<<c<<" za"<<workTime<<" sec";
 
 
    
    getch();
    return 0;
}
время выполнения 0секунд.
Может кому понадобится
Yandex
Объявления
07.06.2011, 20:53     Мультипликативно обратный элемент
Ответ Создать тему
Опции темы

Текущее время: 05:41. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru