Found with PFGW Version 3.7.5

512^8729-8729^512 is 2-PRP! (9.9537s+0.0008s)
512^8729-8729^512 is 3-PRP! (9.9343s+0.0007s)
512^8729-8729^512 is 5-PRP! (10.1872s+0.0008s)
512^8729-8729^512 is 7-PRP! (10.4854s+0.0008s)
512^8729-8729^512 is 11-PRP! (9.8138s+0.0007s)

Primality testing 512^8729-8729^512 [N-1/N+1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 3
Running N-1 test using base 7
Running N-1 test using base 13
Running N+1 test using discriminant 19, base 1+sqrt(19)
Calling N+1 BLS with factored part 0.08% and helper 0.05% (0.28% proof)
512^8729-8729^512 is Fermat and Lucas PRP! (68.3673s+0.0014s)

To be completed...