Estuve probando los casos de prueba y obtuve algunas diferencias que quería compartir con todos, capaz que me pueden corregir o podemos ver donde está el problema.
sage: r1,r2,r3,r4=(1299743, 1299827, 1299833, 1299887) #r1==p,r2==q
sage: t3, t4 = 392357,538006
sage: d3, d4 = 67575,878571
sage: dP, dQ = 848189,303739
sage: qInv = 355905
sage: rsadp(((r1,r2,dP,dQ,qInv), [(r3,d3,t3),(r4,d4,t4)]),e)
1008117944153308176100846
yo obtengo que el valor es 2781226353634542850957010
lo corrí a "mano" para verificar y bueno, acá dejo lo que hice, por favor avisenme donde está el error si lo encuentran
e=(2**16) -1
r1,r2,r3,r4=(1299743, 1299827, 1299833, 1299887)
t3, t4 = 392357,538006
d3, d4 = 67575,878571
dP, dQ = 848189,303739
qInv = 355905
m1= pow(e,dP,r1) #271185
m2= pow(e,dQ,r2) #833310
m3= pow(e,d3,r3) #198195
m4= pow(e,d4,r4) #377593
h=(m1-m2)*qInv %r1 #1142893
m=m2+r2*h #1485564012821
R=r1 #1299743
R=R*r2 # 1689441044461
h=((m3-m)*t3)%r3 #755316
m=m+R*h #1276063337502117497
R=R*r3 #2195991221144875013
h=((m4-m)*t4)%r4 #1266501
m=m+R*h #2781226353634542850957010
print m
Quiero aclarar que use la función pow para asegurarme de no tener problemas con el algoritmo de exponenciación rápida que implemente.
No tengo ánimos de ofender a nadie, sólo quiero compartir mis inquietudes, espero la respuesta tanto del equipo docente como de cualquier otro compañero de clase, Saludos