DSA

import hashlib
from numbthy import *
import math
import hashlib
import itertools

g = 32253863826534580358551120804705900997943177731800264654377534119426401203425184431245632621640646742240939070345623389230557697826015390534483816181075525266195392072345240563646039836711386787248808493842434440315833588970263283033989623260810135075331613124973950747929079888237567546843099775628192130746
p = 89884656743115795386465259539451236680898848947115328636715040578870002598005102946960601910983943855925747713347194276719036880337932178165913634792410605756306943020227796604882868430393341237983464052707923659888878988882604697720623737927532345571650089499821263380908797555719089333168999002682832217669
y = 66692092670232924558458104644803574153454539662307443445813095457088123314138575160650493089203833235095548056252895803339272284336535171676131892751362093298545076060181136977468236383758919953298932170317565596741010165921297323256727053552626095671043458875558348596561823902994897347221830920945041021216
q = 867357578109983745841597164719450559710168288891

(m0, r0, s0) = ("LSE", 743428439266971787959628320180555405854947137342, 114094956363024567153189165333809045591977705861)

(m1, r1, s1) = ("is", 743428439266971787959628320180555405854947137342, 31958627208726330920773970686450941312433435997)

(m2, r2, s2) = ("fun!", 743428439266971787959628320180555405854947137342, 454235500983024228045553020250799181228372703913)

h1 = 0xb47f363e2b430c0647f14deea3eced9b0ef300ce
h2 = 0xf88b2110174539c672f781da07ae2c042eaebdaa


k = (invmod((s1-s2),q)*(h1-h2)) % q
x = -(invmod(r1*(s2-s1),q)*(s2*h1-s1*h2)) % q

print " x = " + str(x)