Если я правильно понял, вы ищете Обратный мод . Математика выглядит следующим образом:
ab = a^b % p
ab + c*p = a^b
log(ab+c*p)/log(a) = b
(ab+c*p)^(1/b) = a
, где c - целое число c={ 0,1,2,3,4... }, преобразовывающее между нормальной и модульной арифметикой. Так что в вашем случае вы хотите вычислить b. Проблема в том, что log(ab+c*p)/log(a) растет очень медленно с увеличением c, если p не намного больше, чем a. Таким образом, в таком случае быстрее использовать все комбинации b, пока в C ++ не будет найдено что-то похожее:
//---------------------------------------------------------------------------
ALU32 alu;
DWORD modmul(DWORD a,DWORD b,DWORD p) // ans = a*b % p
{
DWORD ch,cl,c,d;
alu.mul(ch,cl,a,b);
alu.div(c,d,ch,cl,p);
return d;
}
//---------------------------------------------------------------------------
DWORD modinv(DWORD a,DWORD p) // a * ans % p = 1
{
DWORD b,c,db,dc,i=0;
db=p/a;
dc=db*a;
for (b=1,c=a;b<p;i++)
{
if (c==1) return b;
b+=db; c+=dc;
while (c<p){ b++; c+=a; }
c-=p;
}
return 0;
}
//---------------------------------------------------------------------------
DWORD modpow(DWORD a,DWORD b,DWORD p) // ans = a^b % p
{ // b is not mod(p) !
DWORD i,d=1;
for (a%=p,i=0;i<32;i++,b<<=1)
{
d=modmul(d,d,p);
if (DWORD(b&0x80000000)) d=modmul(d,a,p);
}
return d;
}
//---------------------------------------------------------------------------
DWORD imodpow(DWORD ab,DWORD a,DWORD p) // ab = a^ans % p
{ // ans is not mod(p) !
DWORD b,AB;
for (AB=1,b=0;;)
{
if (AB==ab) return b;
b++; if (!b) return 0;
AB=modmul(AB,a,p);
}
}
//---------------------------------------------------------------------------
грубо, это SLOOOOW, поэтому оно используется для криптографии. Также будьте осторожны, существует несколько допустимых решений , и первое найденное может быть не тем, которое вы ищете, поэтому вам нужно добавить дополнительные условия ...
ALU32.h может бытьможно найти здесь Не могу сделать, чтобы значение распространялось через перенос
И модульная арифметика основана на этом: Модульная арифметика и оптимизация NTT (конечное поле DFT)
Вот пример для сравнения (игнорируйте функции VCL и TBEG / TED / TSTR):
DWORD a=87654321,b=12345678,p=0xC0000001,ab,bb;
tbeg(); ab=modpow(a,b,p); tend(); mm_log->Lines->Add(AnsiString().sprintf("%8u^%8u mod %u = %u ",a,b ,p,ab)+tstr(1));
tbeg(); bb=imodpow(ab,a,p); tend(); mm_log->Lines->Add(AnsiString().sprintf("%8u^%8u mod %u = %u ",a,bb,p,ab)+tstr(1));
и вывод:
87654321^12345678 mod 3221225473 = 3038293251 [ 0.002 ms]
87654321^12345678 mod 3221225473 = 3038293251 [ 421.910 ms]
PS.
Могут быть некоторые более продвинутые подходы из теории чисел, если p особенный, как простое, составное из двух простых или даже n-го корня из единства ... но это в галактике очень далеко от моей досягаемостиэкспертизы.
[edit1]
из недавно опубликованного вопроса , наконец, стало более ясно, что вы на самом деле просто хотели модульное обратное и не имеете ничего общего с imodpow. Итак, что вы хотите, это:
a*b % p = 1
, где b неизвестно, поэтому просто попробуйте все b в возрастающей манере, где a*b % p просто усекается на p до нуля, и если результат1 вы нашли свой ответ. Я обновил код выше с помощью функции modinv, сделав именно это + некоторая оптимизация. Однако я думаю, что есть еще более быстрые подходы для этого с использованием GCD или чего-то еще.
Вот еще один тестовый образец:
DWORD a=87654321,b=12345678,p=0xC0000001,ab,bb;
ab=modmul(a,b,p);
tbeg(); bb=modinv(b,p); tend(); mm_log->Lines->Add(AnsiString().sprintf(" 1/%8u mod %u = %u ",b,p,bb)+tstr(1));
tbeg(); a =modmul(b,bb,p); tend(); mm_log->Lines->Add(AnsiString().sprintf("%8u*%8u mod %u = %u ",b,bb,p,a)+tstr(1));
tbeg(); a =modmul(ab,bb,p); tend(); mm_log->Lines->Add(AnsiString().sprintf("%8u*%8u mod %u = %u ",ab,bb,p,a)+tstr(1));
И вывод:
1/12345678 mod 3221225473 = 165081805 [ 4.999 ms]
12345678*165081805 mod 3221225473 = 1 [ 0.000 ms]
652073126*165081805 mod 3221225473 = 87654321 [ 0.000 ms]