-1
$\begingroup$

So, I have an four numbers.

There is they are:

Number 1 is

40008260280899465341031700284668165694305281399205262735419849961365494809955

Number 2 is

82350526090533023720340378009795932810949001557338040412858442884672237587320

Number 3 is

115792089237316195423570985008687907853269984665640564039457584007908834671663

Number 4 is

0

I must calculate an fourth number, which at the moment equals to zero.

To do that, I must perform four steps of math operations.

1. Multiply Number 1 by Number 1

The result of this step will be:

1600660890704197765354479495339625405951583926360287119453582016817491244540713053191394166818590707196837509107255928642787944538394204779614041567102025

2. Subtract Number 2 from number given at step 1

The result of this step will be:

1600660890704197765354479495339625405951583926360287119453582016817491244540630702665303633794870366818827713174444979641230606497981346336729369329514705

3. Subtract Number 2 from number given at step 2

The result of this step will be:

1600660890704197765354479495339625405951583926360287119453582016817491244540548352139213100771150026440817917241634030639673268457568487893844697091927385

4. Find a remainder of division (result of step 3) / Number 3

The result of this step will be:

57596313968696056513592514942606311130102873379708317985822131243580561204901

Result of #4 will be Number 4.

Can I get result of #4 in some way, where none of results steps will be greater than:

115792089237316195423570985008687907852837564279074904382605163141518161494337

Is it possible to get this result but using only simple arithmetic functions?

Like addition, subtraction, multiplication, division, ...?

UPD.: I'm tried @paul-sinclair answer. If I'm correct, I must perform following steps:

step1 = n1 mod n3
step2 = n2 mod n3
step3 = step1 * step1
step4 = step2 * 2
step5 = step3 mod n3
step6 = step5 - step4
step7 = step6 mod n3

It gives right result, but step3 gives very big number, greater than written above.

$\endgroup$
10
  • 1
    $\begingroup$ So you want the remainder from $\frac{n_1^2-2n_2}{n_3}$ $\endgroup$
    – Chinny84
    Sep 2, 2015 at 23:03
  • $\begingroup$ Thank you. As I understand, yes. I want the remainder from this. I'm searching for some magic way to get Number 4 where result of every step can't be greater than number written above. The problem comes in at first step. As a result, this way of calculation is unsuitable to selected condition. P.S.: I'm got that I must ask about this in Math way, but my Math so weak... $\endgroup$
    – Kechup
    Sep 2, 2015 at 23:49
  • $\begingroup$ Can you give some context to the question. Why do you want to do this? $\endgroup$
    – RowanS
    Sep 3, 2015 at 0:04
  • $\begingroup$ @RowanS yes, of course. I'm trying to create a key pair using secp256k1 curve. At some moment I want to perform this operations, but I have a conditions when I can't use numbers greater than I wrote. So I think that maybe that is possible to avoid this steps and perform this calculation in another way. $\endgroup$
    – Kechup
    Sep 3, 2015 at 0:16
  • 1
    $\begingroup$ @Kechup - this is why I said it depends on the context. I don't know what is limiting you to numbers less than your limit. In certain situations, (step1 * step1 mod n3) can be considered 1 step. In others it can't. I don't know which is true for you. $\endgroup$
    – Paul Sinclair
    Sep 3, 2015 at 2:32

1 Answer 1

Reset to default
0
$\begingroup$

Modular arithematic: the remainder from dividing $a$ by $n$ is denoted by $a \mod n$ (this is a comp science notation by the way - mathematicians generally use "mod" a bit differently). The thing is the remainder is fairly well behaved (Edited to add Lubin's correction): $$(a + b) \mod n = (a \mod n) + (b \mod n) \mod n$$ $$ ab \mod n = (a \mod n)(b \mod n) \mod n$$ etc. So your problem is to find $ n_1^2 -2n_2 \mod n_3 $.

The trick is to take the remainder first: $$ n_1^2 -2n_2 \mod n_3 = \left ( (n_1 \mod n_3)^2 \mod n_3 - 2(n_2 \mod n_3) \right ) \mod n_3$$

That is, at each point as soon as any intermediary calculation raises above $n_3$, we take the remainder $\mod n_3$ again to make it smaller. Because of how remainders work, this will give the same answer in the end.

$\endgroup$
5
  • $\begingroup$ For me, it's a genius answer. Very very big THANK YOU! I will try this soon! $\endgroup$
    – Kechup
    Sep 3, 2015 at 0:29
  • 1
    $\begingroup$ If you’re really talking computer-science notation, your first two displayed equations are not true: if $a=12$ and $b=13$ and $n=5$, then the left-hand side of your first equation is $1$, while the right-hand side is $6$. You have to apply “mod” once more on the right-hand side. $\endgroup$
    – Lubin
    Sep 3, 2015 at 1:02
  • $\begingroup$ @Paul Sinclair, I have updated my question. I'm tried your solution. It works, but at one step I have number that very big. $\endgroup$
    – Kechup
    Sep 3, 2015 at 1:24
  • $\begingroup$ @Lubin - true. and similarly for the $ab$ equation. I did account for that in the final expression, but forgot to add it into these identities. $\endgroup$
    – Paul Sinclair
    Sep 3, 2015 at 1:52
  • 1
    $\begingroup$ @Kechup - thank you for marking this as an answer, except since it doesn't fully solve your problem, that is pre-mature. It may be that someone out there has another trick that will solve the final issue. I think it is possible to reduce the numbers by turning the mod around: working with $n_3 \mod step1$, but I haven't worked out the details. $\endgroup$
    – Paul Sinclair
    Sep 3, 2015 at 3:00

Not the answer you're looking for? Browse other questions tagged .