Mathematics desk
< January 5	<< Dec \| January \| Feb >>	Current desk >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

January 6

Calculating the inverse of a function

The function in question y = f(x) = x * p mod q, where x is a natural number, p and q are primes, and x, p, q are all roughly the same in magnitude (eg: x = 26, p = 29, q = 31). I am trying to compute the inverse, x = g(y), but the set of solutions seems elusive. Earl of Arundel (talk) 13:54, 6 January 2023 (UTC)[reply]

If you have the modular multiplicative inverse of

p,

that is, the number

p^{{-}1}

satisfying

p^{{-}1}p\equiv 1~~({\text{mod}}~q),

the equation

xp\equiv y~~({\text{mod}}~q)

is solved by

x=p^{{-}1}y.

The modular multiplicative inverse can be computed efficiently, as explained in the article, by solving an instance of Bézout's identity, for example by using the extended Euclidean algorithm. An alternative (but equivalent) approach is to compute the convergents of the continued fraction expansion of

p/q.

Letting

p_{\ast }/q_{\ast }

denote the penultimate convergent, the equality

|p_{\ast }q-q_{\ast }p|=1

holds, so either

q_{\ast }

or

-q_{\ast }

is the multiplicative inverse of

p.

--Lambiam 15:07, 6 January 2023 (UTC), so[reply]

For example, the successive convergents of

{\frac {29}{31}}

are

{\frac {0}{1}},{\frac {1}{1}},{\frac {14}{15}},{\frac {29}{31}}.

Indeed,

15\times 29=435=1+14\times 31,

so

29x\equiv y~~({\text{mod}}~31)

is solved by

x=15y.

--Lambiam 15:39, 6 January 2023 (UTC)[reply]

Ah yes, of course! Ok, so this should be easy even if x, p, and q are largish (say 300 decimal digits), given that the time complexity of those algorithms are on the order of log(x)^2? Earl of Arundel (talk) 16:09, 6 January 2023 (UTC)[reply]

Yes, it is all polynomial time in the length of the input. So don't use this as the basis of a cryptographical protocol. :) --Lambiam 16:30, 6 January 2023 (UTC)[reply]

Awesome. Thanks again, Lambiam. Cheers! Earl of Arundel (talk) 16:38, 6 January 2023 (UTC)[reply]

Sides of a hexagonal triangle

What rule is there for the sides of a hexagonal triangle a, b, and c?? This means that the angle between a and b is a hexagonal angle; exactly 120 degrees. We know that $1,1,sqrt(3)$ is a hexagonal triangle, but how would you find b in a hexagonal triangle if a is 1 and c is 2?? Georgia guy (talk) 16:13, 6 January 2023 (UTC)[reply]

Using the cosine rule will give you a quadratic equation for b (with two solutions). AndrewWTaylor (talk) 16:26, 6 January 2023 (UTC)[reply]

Only one of the two solutions for

b

will be positive. --Lambiam 20:45, 6 January 2023 (UTC)[reply]

Tangential point, but I'm not familiar with this sense of "hexagonal triangle", which on its face sounds a bit like "square circle". GG, did you just make this up as a nonce term? As far as that goes I'm not familiar with the notion of "hexagonal angle" either. --Trovatore (talk) 21:11, 6 January 2023 (UTC) [reply]

Also, in mathematical parlance, a hexagon is any polygon with six sides. The 120° angles are specific to regular hexagons. --Lambiam 23:13, 6 January 2023 (UTC)[reply]

Am I mistaken in my understanding. Six equilateral triangles form a hexagon, so is not a 60/60/60 degree triangle this "hexagonal triangle"? -- SGBailey (talk) 18:04, 8 January 2023 (UTC)[reply]

The term has no commonly agreed meaning. At least one person thought it means this. --Lambiam 19:04, 8 January 2023 (UTC)[reply]

Here is another way of forming a hexagon with six congruent triangles. --Lambiam 10:54, 9 January 2023 (UTC)[reply]

I thought he explained what he meant okay and people do make up terms even if they're not destined to catch on, here's a right wiggly triangle problem for instance :-) NadVolum (talk) 12:53, 9 January 2023 (UTC)[reply]

Oh, for sure. If I'm honest, I didn't think it was a particularly good nonce term, but my comment wasn't meant as any serious criticism of Georgia Guy. Still, it's perhaps worth pointing out when terminology isn't standard, for the benefit of others who read the exchange. --Trovatore (talk) 03:20, 11 January 2023 (UTC)[reply]