как сделать сабж на С? слишком много знаков получается,а куда такое большое число писать? ни в один тип не влезешь, а надо

Здравствуйте, temik, Вы писали:

T>как сделать сабж на С? слишком много знаков получается,а куда такое большое число писать? ни в один тип не влезешь, а надо
Про умножение столбиком слышал?

Здравствуйте, WolfHound, Вы писали:

WH>Про умножение столбиком слышал?
Слышал, только как его реализовать на асме?

Здравствуйте, temik, Вы писали:

WH>>Про умножение столбиком слышал?
T>Слышал, только как его реализовать на асме?
Обязательно на асме? Замучаешься.
А идея простая. Число хранится как массив чисел 0 <= a[n] < 10^m. Все число А = sum(a[i]*10^(m*i).
Т.е. это просто запись числа впозиционной системе счисления по основанию 10^m. В принципе основание можно выбрать и другое, но с этим удобно осуществлять вывод.
Алгоритмы для арифмитических действий кроме деления — тривиальные, справится школьник ( проверено! ). Деление тоже тривиально, но школьник может и затормозить.
Читать Кнута, есть на lib.ru. Так же нечто есть на algolist, но я не смотрел.

Здравствуйте, Рома Мик, Вы писали:

WH>>>Про умножение столбиком слышал?
T>>Слышал, только как его реализовать на асме?

Надо думать, поскольку в соседнем топике temik — а речь идет об RSA, то имеется в виду возведение в степень по некоему модулю.
Простейший алгоритм модульного возведения в степень:

на входе
g — число
e — степень
m — модуль

на выходе
g ^ e mod m

1. A = 1, S = g
2. while( e != 0 )
2.1 if e нечетное A = ( A * S ) % m
2.2 e = e / 2
2.3 if( e != 0 ) S = S * S % m
3. return A

при этом разрядность результатов промежуточных умножений не вылезает за m^2 — 2.
так что если m <= 2^16 то все операции прекрасно можно производить в 32-х битных регистрах.

Здравствуйте, temik, Вы писали:

T>как сделать сабж на С? слишком много знаков получается,а куда такое большое число писать? ни в один тип не влезешь, а надо
Попробуй через строку, или несколько строк записать результат

Здравствуйте, Рома Мик, Вы писали:

РМ>Здравствуйте, temik, Вы писали:

WH>>>Про умножение столбиком слышал?
T>>Слышал, только как его реализовать на асме?
РМ>Алгоритмы для арифмитических действий кроме деления — тривиальные, справится школьник ( проверено! ). Деление тоже тривиально, но школьник может и затормозить.
Ой, надо же в степень возводить.
Ну, собственно, надо считать экспоненту, логарифм... Кой-какие алгоритмы есть на algorithm.narod.ru. Конкретно экспонента algorithm.narod.ru/el/sicoex.html.

Еще целочисленное возведение в степень ( можно и по модулю ): на каждом шаге домножаем наше число само на себя, так что получаем вначале a^2, потом a^4, потом a^8 и т.д. и иногда домножаем наш результат на текущее число. Например если надо a^10, то получим a^10 = a^2 * a^8. Т.е. надо подобрать сумму разных степеней двойки, чтобы получилась нужная степень. Нетрудно догадаться, что домнажать надо когда установлен соответствующий бит двоичного представления искомой степени. В моем примере 10 = 1010b, а степени такие a^1, a^2, a^4, a^8.

Здравствуйте, Dmitry Kukushkin, Вы писали:

DK>так что если m <= 2^16 то все операции прекрасно можно производить в 32-х битных регистрах.

m <= 2^16 для RSA интереса не представляют

Здравствуйте, desperado_gmbh, Вы писали:

DK>>так что если m <= 2^16 то все операции прекрасно можно производить в 32-х битных регистрах.

_>m <= 2^16 для RSA интереса не представляют

Все вопросы к преподу. Это он так temik-у делать велел

Здравствуйте, temik, Вы писали:

T>как сделать сабж на С? слишком много знаков получается,а куда такое большое число писать? ни в один тип не влезешь, а надо

Рекомендую посетить GNU MP. Там есть библиотека работы с числами (большими). Можно или использовать саму библиотеку или посмотреть как там реализованы все необходимые тебе вещи.

Здравствуйте, WeCom, Вы писали:

WC>Рекомендую посетить GNU MP. Там есть библиотека работы с числами (большими). Можно или использовать саму библиотеку или посмотреть как там реализованы все необходимые тебе вещи.

Так ему ведь не нужно больших чисел! У него модуль<=999! Это все делается без длинной арифметики

считает правильно(на калькуляторе виндовом проверял), я результат шфировки/дешифровки неправильный

int crypt(int number,int power,int mod)
{
    int count,divcount,numcp,module,modcp;
    
    module=mod;
    modcp=module;
    numcp=number;
    int mull;
    mull=number;
    
    //int mas[65535],mas2[65535],mas3[65535];
    int  *mas,*mas2,*mas3;
    mas=new int[65535];
    mas2=new int[65535];
    mas3=new int[65535];
    count=0;
    divcount=0;
    while(numcp)
    {
        count++;
        numcp=(numcp/10);
    }
    while(modcp)
    {
        divcount++;
        modcp=(modcp/10);
    }
    for(int i=0;i<65535;i++)
    {
        mas[i]=0;
        mas2[i]=0;
        mas3[i]=0;
    }
    for(i=0;i<count;i++)
    {
        mas[i]=(number%10);
        mas2[i]=(number%10);
        number=(number/10);
    }
    
//начало возведения в степень
    for(int p=2;p<=power;p++)
    {
    //начало умножения
    for(int m=2;m<=mull;m++)
    {
    for(i=0;i<count;i++)
    {
        mas[i]+=mas2[i];
        if(mas[i]>=10)
        {
            mas[i]=(mas[i]%10);
            mas[i+1]+=1;
            if((i+1)>(count-1))
            {
                count++;
            }
        }
    }

    //конец умножения
    }
    for(i=0;i<count;i++)
    {
        mas2[i]=mas[i];
    }

//конец возведения в степень
}
//cout<<mas[0]<<mas[1]<<mas[2];

    
//for(int fff=1;fff<=170;fff++)

    int sum;
    sum=0;

        for(int ad=0;ad<count;ad++)
            {
                if(ad<5)
                {
                sum+=((int)pow(10,ad)*mas[ad]);
                sum=sum%module;
                }
                else
                {
                    int ab;
                    ab=ad;
                    int tmpsum;
                    tmpsum=0;
                    tmpsum=10*mas[ad];
                    tmpsum=tmpsum%module;
                    for(ab=2;ab<=ad;ab++)
                    {
                        tmpsum=((tmpsum*10)%module);
                    }
                    sum+=tmpsum;
                }
                sum=sum%module;
            }
        
            
delete[] mas;
delete[] mas2;
delete[] mas3;    

    cout<<'\n'<<sum;
    return sum;
    }

или может на ключи для RSA есть ограничения какие?

Здравствуйте, temik, Вы писали:

T>как сделать сабж на С? слишком много знаков получается,а куда такое большое число писать? ни в один тип не влезешь, а надо

pow(255, 999) ==
136031740096639497298870615926611790704862006368595867449565848775269427078660031413429705
673830817683803526103125170721997104832267802994538924026472596144389444098254298443706334
790798033004027259891995227885892233111979929318562090823458947137547439948074085156585258
999415058281305316181752312304745890303303516570929812416117327866737649234828167282343590
530731509633479506493547154440306622653739694406904424304909260999698369279445724498344473
747154133837782547246782841707127324881039299514091427255885198898985132684535357556903419
823423707610005250141915042295947288633273569669222477696301739605764143197101695868649358
320396385903136165288187018501928068806038460728899647864934624962420442166625188531155888
793386875128295165384699789336366094643300379367528564226374708934888789979698196483587229
960540443569767526893316098563788009920818303936762445852994777752821669675288070919977520
432221580536724954114378401830051063045737618460199448901996255649575991256252137036809772
216429522489753551459152039844137975880617788808759077279754201172765598747728526170542299
685993102365445309895552628208027859881975513835532087235922527389603203132529333179686163
908323836316528959303392992929266736481395957200897569801987703737013902930349887079797791
943909967543019270540147073697177958329453669704969187239184797595539909795398257798126904
875208211418400851547461963877036646840542609981353738283637060469943484078082562475503559
212823166149467038027741051051026804228503895787961183142619383042925119820892037508060657
252285035183208023125812053473530171950228977217234731287421790440700269734732348969251408
060831963943132166122541937975522500350563061102817094302203369324301601010331026100200623
536361451256091435297552252315447617743096368565545992759066118543347961952974610963272112
898369124054260632752567218410687383645787797011853599191036734972487605647473545980297215
872010313219782260326517508803718678898308667596133361447423237523418728532021262287668707
314239610778679106686598676495028060255559761975859585295367092144401007314837551445796715
059756670749368106078893887056283238828625529693297234605861418230977091023728556762969380
989708793190509874485191282175758777577895865305831397926902898380425362704899418386248586
347500334552553656627231845766601377261766005670736311975123757258361157019704177968842075
09280133512306144304994902360927966356030083261430263519287109375